skip to main content


Title: Minimal Solvers for Mini-Loop Closures in 3D Multi-Scan Alignment
3D scan registration is a classical, yet a highly useful problem in the context of 3D sensors such as Kinect and Velodyne. While there are several existing methods, the techniques are usually incremental where adjacent scans are registered first to obtain the initial poses, followed by motion averaging and bundle-adjustment refinement. In this paper, we take a different approach and develop minimal solvers for jointly computing the initial poses of cameras in small loops such as 3-, 4-, and 5-cycles1. Note that the classical registration of 2 scans can be done using a minimum of 3 point matches to compute 6 degrees of relative motion. On the other hand, to jointly compute the 3D reg- istrations in n-cycles, we take 2 point matches between the first n−1 consecutive pairs (i.e., Scan 1 & Scan 2, . . . , and Scan n − 1 & Scan n) and 1 or 2 point matches between Scan 1 and Scan n. Overall, we use 5, 7, and 10 point matches for 3-, 4-, and 5-cycles, and recover 12, 18, and 24 degrees of transformation variables, respectively. Using simulations and real-data we show that the 3D registration using mini n-cycles are computationally efficient, and can provide alternate and better initial poses compared to standard pairwise methods.  more » « less
Award ID(s):
1764071
NSF-PAR ID:
10093739
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN:
2332-564X
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Obeid, Iyad ; Picone, Joseph ; Selesnick, Ivan (Ed.)
    The Neural Engineering Data Consortium (NEDC) is developing a large open source database of high-resolution digital pathology images known as the Temple University Digital Pathology Corpus (TUDP) [1]. Our long-term goal is to release one million images. We expect to release the first 100,000 image corpus by December 2020. The data is being acquired at the Department of Pathology at Temple University Hospital (TUH) using a Leica Biosystems Aperio AT2 scanner [2] and consists entirely of clinical pathology images. More information about the data and the project can be found in Shawki et al. [3]. We currently have a National Science Foundation (NSF) planning grant [4] to explore how best the community can leverage this resource. One goal of this poster presentation is to stimulate community-wide discussions about this project and determine how this valuable resource can best meet the needs of the public. The computing infrastructure required to support this database is extensive [5] and includes two HIPAA-secure computer networks, dual petabyte file servers, and Aperio’s eSlide Manager (eSM) software [6]. We currently have digitized over 50,000 slides from 2,846 patients and 2,942 clinical cases. There is an average of 12.4 slides per patient and 10.5 slides per case with one report per case. The data is organized by tissue type as shown below: Filenames: tudp/v1.0.0/svs/gastro/000001/00123456/2015_03_05/0s15_12345/0s15_12345_0a001_00123456_lvl0001_s000.svs tudp/v1.0.0/svs/gastro/000001/00123456/2015_03_05/0s15_12345/0s15_12345_00123456.docx Explanation: tudp: root directory of the corpus v1.0.0: version number of the release svs: the image data type gastro: the type of tissue 000001: six-digit sequence number used to control directory complexity 00123456: 8-digit patient MRN 2015_03_05: the date the specimen was captured 0s15_12345: the clinical case name 0s15_12345_0a001_00123456_lvl0001_s000.svs: the actual image filename consisting of a repeat of the case name, a site code (e.g., 0a001), the type and depth of the cut (e.g., lvl0001) and a token number (e.g., s000) 0s15_12345_00123456.docx: the filename for the corresponding case report We currently recognize fifteen tissue types in the first installment of the corpus. The raw image data is stored in Aperio’s “.svs” format, which is a multi-layered compressed JPEG format [3,7]. Pathology reports containing a summary of how a pathologist interpreted the slide are also provided in a flat text file format. A more complete summary of the demographics of this pilot corpus will be presented at the conference. Another goal of this poster presentation is to share our experiences with the larger community since many of these details have not been adequately documented in scientific publications. There are quite a few obstacles in collecting this data that have slowed down the process and need to be discussed publicly. Our backlog of slides dates back to 1997, meaning there are a lot that need to be sifted through and discarded for peeling or cracking. Additionally, during scanning a slide can get stuck, stalling a scan session for hours, resulting in a significant loss of productivity. Over the past two years, we have accumulated significant experience with how to scan a diverse inventory of slides using the Aperio AT2 high-volume scanner. We have been working closely with the vendor to resolve many problems associated with the use of this scanner for research purposes. This scanning project began in January of 2018 when the scanner was first installed. The scanning process was slow at first since there was a learning curve with how the scanner worked and how to obtain samples from the hospital. From its start date until May of 2019 ~20,000 slides we scanned. In the past 6 months from May to November we have tripled that number and how hold ~60,000 slides in our database. This dramatic increase in productivity was due to additional undergraduate staff members and an emphasis on efficient workflow. The Aperio AT2 scans 400 slides a day, requiring at least eight hours of scan time. The efficiency of these scans can vary greatly. When our team first started, approximately 5% of slides failed the scanning process due to focal point errors. We have been able to reduce that to 1% through a variety of means: (1) best practices regarding daily and monthly recalibrations, (2) tweaking the software such as the tissue finder parameter settings, and (3) experience with how to clean and prep slides so they scan properly. Nevertheless, this is not a completely automated process, making it very difficult to reach our production targets. With a staff of three undergraduate workers spending a total of 30 hours per week, we find it difficult to scan more than 2,000 slides per week using a single scanner (400 slides per night x 5 nights per week). The main limitation in achieving this level of production is the lack of a completely automated scanning process, it takes a couple of hours to sort, clean and load slides. We have streamlined all other aspects of the workflow required to database the scanned slides so that there are no additional bottlenecks. To bridge the gap between hospital operations and research, we are using Aperio’s eSM software. Our goal is to provide pathologists access to high quality digital images of their patients’ slides. eSM is a secure website that holds the images with their metadata labels, patient report, and path to where the image is located on our file server. Although eSM includes significant infrastructure to import slides into the database using barcodes, TUH does not currently support barcode use. Therefore, we manage the data using a mixture of Python scripts and manual import functions available in eSM. The database and associated tools are based on proprietary formats developed by Aperio, making this another important point of community-wide discussion on how best to disseminate such information. Our near-term goal for the TUDP Corpus is to release 100,000 slides by December 2020. We hope to continue data collection over the next decade until we reach one million slides. We are creating two pilot corpora using the first 50,000 slides we have collected. The first corpus consists of 500 slides with a marker stain and another 500 without it. This set was designed to let people debug their basic deep learning processing flow on these high-resolution images. We discuss our preliminary experiments on this corpus and the challenges in processing these high-resolution images using deep learning in [3]. We are able to achieve a mean sensitivity of 99.0% for slides with pen marks, and 98.9% for slides without marks, using a multistage deep learning algorithm. While this dataset was very useful in initial debugging, we are in the midst of creating a new, more challenging pilot corpus using actual tissue samples annotated by experts. The task will be to detect ductal carcinoma (DCIS) or invasive breast cancer tissue. There will be approximately 1,000 images per class in this corpus. Based on the number of features annotated, we can train on a two class problem of DCIS or benign, or increase the difficulty by increasing the classes to include DCIS, benign, stroma, pink tissue, non-neoplastic etc. Those interested in the corpus or in participating in community-wide discussions should join our listserv, nedc_tuh_dpath@googlegroups.com, to be kept informed of the latest developments in this project. You can learn more from our project website: https://www.isip.piconepress.com/projects/nsf_dpath. 
    more » « less
  2. In recent years, LiDAR sensors have become pervasive in the solutions to localization tasks for autonomous systems. One key step in using LiDAR data for localization is the alignment of two LiDAR scans taken from different poses, a process called scan-matching or point cloud registration. Most existing algorithms for this problem are heuristic in nature and local, meaning they may not produce accurate results under poor initialization. Moreover, existing methods give no guarantee on the quality of their output, which can be detrimental for safety-critical tasks. In this paper, we analyze a simple algorithm for point cloud registration, termed PASTA. This algorithm is global and does not rely on point-to-point correspondences, which are typically absent in LiDAR data. Moreover, and to the best of our knowledge, we offer the first point cloud registration algorithm with provable error bounds. Finally, we illustrate the proposed algorithm and error bounds in simulation on a simple trajectory tracking task. 
    more » « less
  3. null (Ed.)
    Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds. 
    more » « less
  4. Metal-mediated cross-coupling reactions offer organic chemists a wide array of stereo- and chemically-selective reactions with broad applications in fine chemical and pharmaceutical synthesis.1 Current batch-based synthesis methods are beginning to be replaced with flow chemistry strategies to take advantage of the improved consistency and process control methods offered by continuous flow systems.2,3 Most cross-coupling chemistries still encounter several issues in flow using homogeneous catalysis, including expensive catalyst recovery and air sensitivity due to the chemical nature of the catalyst ligands.1 To mitigate some of these issues, a ligand-free heterogeneous catalysis reaction was developed using palladium (Pd) loaded into a polymeric network of a silicone elastomer, poly(hydromethylsiloxane) (PHMS), that is not air sensitive and can be used with mild reaction solvents (ethanol and water).4 In this work we present a novel method of producing soft catalytic microparticles using a multiphase flow-focusing microreactor and demonstrate their application for continuous Suzuki-Miyaura cross-coupling reactions. The catalytic microparticles are produced in a coaxial glass capillary-based 3D flow-focusing microreactor. The microreactor consists of two precursors, a cross-linking catalyst in toluene and a mixture of the PHMS polymer and a divinyl cross-linker. The dispersed phase containing the polymer, cross-linker, and cross-linking catalyst is continuously mixed and then formed into microdroplets by the continuous phase of water and surfactant (sodium dodecyl sulfate) introduced in a counter-flow configuration. Elastomeric microdroplets with a diameter ranging between 50 to 300 micron are produced at 25 to 250 Hz with a size polydispersity less than 3% in single stream production. The physicochemical properties of the elastomeric microparticles such as particle swelling/softness can be tuned using the ratio of cross-linker to polymer as well as the ratio of polymer mixture to solvent during the particle formation. Swelling in toluene can be tuned up to 400% of the initial particle volume by reducing the concentration of cross-linker in the mixture and increasing the ratio of polymer to solvent during production.5 After the particles are produced and collected, they are transferred into toluene containing palladium acetate, allowing the particles to incorporate the palladium into the polymer network and then reduce the palladium to Pd0 with the Si-H functionality present on the PHMS backbones. After the reduction, the Pd-loaded particles can be washed and dried for storage or switched into an ethanol/water solution for loading into a micro-packed bed reactor (µ-PBR) for continuous organic synthesis. The in-situ reduction of Pd within the PHMS microparticles was confirmed using energy dispersive X-ray spectroscopy (EDS), X-ray photoelectron spectroscopy (XPS) and focused ion beam-SEM, and TEM techniques. In the next step, we used the developed µ-PBR to conduct continuous organic synthesis of 4-phenyltoluene by Suzuki-Miyaura cross-coupling of 4-iodotoluene and phenylboronic acid using potassium carbonate as the base. Catalyst leaching was determined to only occur at sub ppm concentrations even at high solvent flow rates after 24 h of continuous run using inductively coupled plasma mass spectrometry (ICP-MS). The developed µ-PBR using the elastomeric microparticles is an important initial step towards the development of highly-efficient and green continuous manufacturing technologies in the pharma industry. In addition, the developed elastomeric microparticle synthesis technique can be utilized for the development of a library of other chemically cross-linkable polymer/cross-linker pairs for applications in organic synthesis, targeted drug delivery, cell encapsulation, or biomedical imaging. References 1. Ruiz-Castillo P, Buchwald SL. Applications of Palladium-Catalyzed C-N Cross-Coupling Reactions. Chem Rev. 2016;116(19):12564-12649. 2. Adamo A, Beingessner RL, Behnam M, et al. On-demand continuous-flow production of pharmaceuticals in a compact, reconfigurable system. Science. 2016;352(6281):61 LP-67. 3. Jensen KF. Flow Chemistry — Microreaction Technology Comes of Age. 2017;63(3). 4. Stibingerova I, Voltrova S, Kocova S, Lindale M, Srogl J. Modular Approach to Heterogenous Catalysis. Manipulation of Cross-Coupling Catalyst Activity. Org Lett. 2016;18(2):312-315. 5. Bennett JA, Kristof AJ, Vasudevan V, Genzer J, Srogl J, Abolhasani M. Microfluidic synthesis of elastomeric microparticles: A case study in catalysis of palladium-mediated cross-coupling. AIChE J. 2018;0(0):1-10. 
    more » « less
  5. Ishikawa, H. ; Liu, CL. ; Pajdla, T. ; Shi, J. (Ed.)
    We propose a novel technique to register sparse 3D scans in the absence of texture. While existing methods such as KinectFusion or Iterative Closest Points (ICP) heavily rely on dense point clouds, this task is particularly challenging under sparse conditions without RGB data. Sparse texture-less data does not come with high-quality boundary signal, and this prohibits the use of correspondences from corners, junctions, or boundary lines. Moreover, in the case of sparse data, it is incorrect to assume that the same point will be captured in two consecutive scans. We take a different approach and first re-parameterize the point-cloud using a large number of line segments. In this re-parameterized data, there exists a large number of line intersection (and not correspondence) constraints that allow us to solve the registration task. We propose the use of a two-step alternating projection algorithm by formulating the registration as the simultaneous satisfaction of intersection and rigidity constraints. The proposed approach outperforms other top-scoring algorithms on both Kinect and LiDAR datasets. In Kinect, we can use 100X downsampled sparse data and still outperform competing methods operating on full-resolution data. 
    more » « less