Feasability Study Proposal:

Applications of

Digital Morse Theory

For Data Exploration

Computer Aided Surgery Incorporated

300 East 33rd Street, Suite 4N

New York, New York 10016 USA

Document Title: Applications of Digital Morse Theory

Date of Submission: 01/28/99 12:38 AM.

Point of Contact: D. B. Karron, Ph.D., C.T.O.

Telephone: (212) 686-8748

Fax: (212) 448-0261.

E-Mail: karron@casi.net

CORRECTED VERSION

 

 

 

Principle Investigator: D. B. Karron, Ph.D.

 

  1. Table of Contents

    2. 1 Table of Contents *

    2 Abstract *

    3 Introduction *

    4 The Significance of Digital Morse Theory *

    5 Statement of the Research Problem *

    Definitions: *

    6 Deliverables *

    6.1 Indexing *

    6.2 Registration *

    6.3 LOD Rendering *

    7 Statement of Work *

    7.1 Project Period *

    7.2 Elements Common to All Subtasks *

    7.2.1 Alpha Pass *

    7.2.2 Beta Pass *

    7.2.3 Additional Pass *

    7.3 Deliverable One Tasks: Indexing *

    7.3.1 Task one Milestones *

    1. Task Two Milestones: Registration *

    8 Project Administration and Personnel *

    8.1 Computer Aided Surgery, Inc. *

    8.2 Principle Investigator *

    9 Budget *

    9.1 Project Cost Elements *

    Notes for cost elements *

    10 References *

    11 Appendix *

    11.1 D. B. Karron, Ph.D. Curriculum Vitae *

    11.1.1 Education *

    11.1.2 Selected Publications: *

    11.1.3 Invited Lectures *

    11.1.4 Employment History *

    11.1.5 Professional Memberships *

    11.1.6 Other Professional Affiliations *

    11.1.7 Professional References *

    11.1.8 Contract Proposals, Funded, Accepted and Funding Pending *

     

  2. Abstract

    3. We propose to demonstrate Digital Morse Theory Criticality Graph Decomposition for Image Registration and Simplification operations in 2 dimensions.

    We will develop and demonstrate a software application which will generate a DMT Graph from a 2D dataset. This application will demonstrate the effect of variously experimentally applied registration error displacement within a sample image dataset on the DMT Graph. By identifying the characteristic effect of registration errors on the Graph, the application will calculate the transformation to achieve a correct registration.

    We intend this research effort on 2D DMT decomposition as preliminary study for future 3 and n-dimensional operations. We believe this 2D demonstration will demonstrate the significant advantage of using a DMT-based approach for solving registration problems over the current state-of-the-art.

  3. Introduction

    4. The rapid proliferation of data in our present Information Age makes it increasingly laborious to extract insight from scientific, military and industrial databases in a timely manner. This avalanche of data presents one of the most significant problems in scientific computing today. This core of this problem is the task of determining which aspect(s) of a dataset are most important for the specific analysis, or how to impose some form of hierarchy upon that dataset.

    Isosurfaces play a crucial role in the analysis, modeling and visualization of data. The inherent properties and utility of these boundaries have not been adequately utilized. We demonstrate that Digital Morse Theory makes it possible to organize all of the different families of surfaces present within a dataset in a hierarchical manner thereby permitting rapid parsing of features of arbitrary scale. Applications of Digital Morse Theory will provide powerful tools for intelligent data abstraction. These tools will provide scientists, strategists, and engineers greater power to explore their data.

    We propose developing applications of Digital Morse Theory in order to demonstrate the benefits of this technique, and to lay the technical groundwork for more advanced applications. We have chosen as our first project a simple 2D-image decomposition. From that we will demonstrate a simple aspect of the decomposition in re-aligning rows of pixels in an image by observing their effect on the graph.

     

  4. The Significance of Digital Morse Theory

    5. Digital Morse Theory permits the organization of data space into hierarchical zones of influence (ZOI), with relations between zones given by the computed tree Criticality Graph. Digital Morse Theory demonstrates many useful properties of the zones and the criticality graph, as proven in our latest paper (Cox & Karron, 1998). For example, each boundary isosurface is completely contained within a zone. Each zone has a range of values associated with it and contains isosurfaces only for isovalues within this range. For any two distinct isovalues within the range, the isosurfaces within the zone are topologically identical. Thus zones contain homeomorphic families.

    Each topologically distinct isosurface bounded object in the dataset is represented by a ZOI and an associated node in the criticality graph. For any particular object, we need only consider the parent ZOI to render the boundary isosurface(s). We can restrict attention to this ZOI. Within the zone one can use our surface construction techniques (SpiderWeb) to further limit the I/O to those readings pertinent to the particular isovalue. In addition we can reduce the tiling density within a ZOI without changing the topology for display and further calculation. For example, one can begin by using every 16th reading (in each dimension) within a zone to construct the isosurface(s). Then one further subdivides (by adding more data readings) and refines the geometry between those readings where there is a large variation in gradient.

    We will demonstrate why and how to apply DMT to extract a Criticality Graph from 2 and more dimensions of data. A region of interest (ROI) within a data space will be indexed using a Criticality Graph, thereby permitting correct registration and management of LOD. Given the modest scope of this pilot project our primary interest will be to demonstrate DMT properties in 2 dimensions.

     

  5. Statement of the Research Problem

Can Digital Morse Theory provide useful insight into a large multidimensional dataset via the Criticality Graph and ZOI’s?

Definitions:

Successful demonstration of the utility of DMT from this feasibility study will enable future work in much more data intensive problems such as establishing bond configuration from x-ray crystallography data, indexing and decomposing molecular electron density fields, constructing DNA-binding drug affinity graphs at various binding thresholds, etc.

 

  1. Deliverables

    2. We will use the Visible Human Project (VHP) dataset as an initial study case in developing our software implementation of Digital Morse Theory. The VHP dataset presents a formable challenge due to its size (greater than eighteen gigabytes) and rich dimensionality (including MRI, CT and RGB). We feel that this will prove a suitable test bed for illustrating the power of Digital Morse Theory-derived applications in exploring large datasets.

    We list the deliverables from this analysis with respect to the indexing, registration and rendering of the VHP dataset.

    1. Indexing

We will deliver a fully decomposed ROI in the form of a Criticality Graph and ZOI’s database.

  1. Pixel Row-wise (2 dimensions)
  2. We will analyze the complexity of our implementation.
  3. We will measure the CPU time, clock time, memory requirements and disk requirements to calculate a full decomposition for our ROI.

    1. Registration

We will calculate a registration transformation matrix from the Criticality Graph and ZOI.

  1. Row-wise (2 dimensions)
  2. Color-wise (for all image modalities, in this case CT, MRI, RGB)

    1. LOD Rendering

CG Display Level of Detail (LOD) resolution control display of a major anatomic structure (A region of the brain to be determined).

  1. We will demonstrate variable resolution tiling of an arbitrary large object in 2D.
  2. We will demonstrate the tiling of this object from full resolution down to a single triangle.
  3. We will demonstrate the display of a combined RGB, CT and MRI object with a common Criticality Graph root. This object will consist of the weighted linear combination of each color object, again with precision topologically constant geometric LOD control.

 

  1. Statement of Work

    1. Project Period

      2. The total duration of this project will be six (6) months.

    2. Elements Common to All Subtasks

      1. Alpha Pass

We will:

      1. Beta Pass

We will:

      1. Additional Pass

We will:

    1. Deliverable One Tasks: Indexing

We will:

      1. Task one Milestones

(1D) Build a shared memory library of all of the pixels in the dataset, which will reside on disk as a swap file. Only those pixels needed in active memory will be swapped in.

  1. Write code to create, edit, and save multiple ROI’s with which to debug the code on known regions.
  2. Write memory management tools to enable rapid allocation, debugging and freeing of large memory tree structures.
  3. Check-pointing code to save the state of long intermediate indexing programs to disk.
  4. Instrument code with semaphores and locks to permit multiple processes concurrent access to pixel data without collision for use with multi-CPU computers when purchased.

    5. (2D) Write the ZOI scanning algorithm code to compile a Criticality Graph for the pixels within a particular slice contained in the ROI.

  5. Write slice pixel display window code and verify that the slice data has been loaded properly into shared memory.
  6. Write arrow display code (to show arrow and vector fields between pixels)
  7. Write code to display the criticalities within a slice.
  8. Write display code to permit viewing of a large and growing tree structure.
  9. Write code to interactively display isocontours over the slice pixels (to demonstrate the behavior of the contours about the criticalities).
  10. Write sub-windows to expand regions of interest of the tree and permit viewing the growth of the tree in real time.
  11. Use locks and semaphores to permit simultaneous construction and display of the tree.
  12. Write code to display ZOI scanning progress within a slice on the slice (view grassfires burning).
  13. Write code to track tree growth statistics during indexing runs.

  1. Task Two Milestones: Registration

  2. We will calculate the value of a registration transformation matrix in each ROI data ZOI Criticality Graph tree to the two adjacent slices without using fiducial markers (fiducials). We will then verify the slice average registration matrix using the VHP external fiducials. Verification scores will be the magnitude and total rotation of the transformation matrix to transform the DMT derived registration into the fiducials derived registration. Fiducial registration will be done using the ‘Blobulation Technique’ to find the center of blobby fiducial marks under operator guidance (Karron 93).

  3. Pixel row registration
  4. Slice registration.
  5. Slice registration verification to fiducials.
  6. Task Three Milestones: LOD Rendering
  7. We will write display code to draw the image completely from the Graph Data, with out any reference to the source pixels.

 

  1. Project Administration and Personnel

    1. Computer Aided Surgery, Inc.

      2. This project will be executed under the auspices of Computer Aided Surgery, Inc. Computer Aided Surgery, Inc. is an innovative research company founded for the purpose of developing medical and biotechnical applications of computational geometry. The offices of Computer Aided Surgery, Inc. are located in Midtown Manhattan. Computer Aided Surgery, Inc. is highly capitalized in terms of high-performance computer hardware and software development tools appropriate for executing this research project.

    2. Principle Investigator

    This project will be administered by D. B. Karron, Ph.D., Chief Technical Officer and founder of Computer Aided Surgery, Inc. D. B. Karron, Ph.D., C.T.O. has numerous years of experience in administering large research projects, including two DARPA SBIR research projects, as well as a number of contract research projects for organizations such as Shepard Patterson, Inc. and the NASA/Yale Commercial Space Center. For further information please see Dr. Karron’s C.V. included in the Appendix.

     

  2. Budget

    1. Project Cost Elements

Notes for cost elements

  1. CASI Overhead rate determined by DCAA for SBIR Phase 1 and Phase 2
  2. Salary for PI based on comparative PI salaries. Includes 30% fringes and benefits

  1. References

    2. Cox, James L, and Karron, D. B. (1998) "Digital Morse Theory with Suggested Applications". Submitted by invitation of Editor, G. Hermann, to Computer Models and Image Processing. Academic Press, San Diego.

    Wegner, Kristen (1998): "DNA-binding Drug Affinity Trees". Technical Report of Computer Aided Surgery, Inc. 1998-3.

    Wegner, Kristen and Karron, D. B. (1998): "Tactical Audio for Surgical Navigation", Submitted by invitation of editor to Journal of the International Society for Computer Aided Surgery (ICAS).

    Vazakas, S. M. (editor) (1998) Virtual Head and Neck Anatomy: Proceedings of NIH/NIDR Strategic Planning Workshop. see http://www.nidr.nih.gov/Strat-plan/headneck.htm

     

  2. Appendix

    1. D. B. Karron, Ph.D. Curriculum Vitae

      2. Address: 300 East 33rd Street, Suite 4N, New York, NY 10016

      E-mail: karron@casi.net

      Phone: 212-686-8748

      Fax: 212-448-0261

      1. Education

      1. Selected Publications:

        2. Cox, James L, and Karron, D. B. (1998) "Digital Morse Theory with Suggested Applications". Submitted by invitation of Editor, G. Hermann, to Computer Models and Image Processing. Academic Press, San Diego.

        Wegner, Kristen and Karron, D. B. (1998): "Tactical Audio for Surgical Navigation", Submitted by invitation of Editor, Richard Bucholz, M.D. to Journal of the International Society for Computer Aided Surgery (ICAS).

        Karron, Daniel B. and Cox, James. "Extracting 3D Objects from Volume Data using Digital Morse Theory. Computer Vision, Virtual Reality, and Robotics in Medicine. Nicholas Ayache, editor. 1995: 481-486.

        Cansano, Selene; Williamson, Sam; Karron, Dan. "Tonotopic Organization of Human Auditory Association Cortex." Brain Research. 663: 38-50.

        Karron, Daniel. "New findings from the SpiderWeb Algorithm: Toward a Digital Morse Theory." Visualization in Biomedical Computing, 1994.

        Karron, Daniel; Grossi, Eugene; Weinreb, Jeffery; Stephenson, Jeffery; Porte, Blaise; "The SpiderWeb algorithm applied in 4D: Using a topologically correct isosurface tracking algorithm to follow the moving surfaces of the heart. 1994 Society of Nuclear Medicine Computer and Instrumentation Council Midwinter Meeting in Seattle, Washington, February 7-9, on "Dedicated Instruments and Computer Processing Techniques for Cardiac and Brain Imaging."

        Williamson, Samuel; Wang, Jia-Zhu; Liu, Zhong-Lin; Karron, Daniel. "Registration and Localization of "Alphons" in Human Cortex." Recent Advances in Biomagnetism. 9th International Conference on Biomagnetism. Vienna, August 14-20, 1993.

        Karron, Daniel; Cox, James; and Mishra, B. "System and Method for Surface Rendering of Internal Structures within the Interior of a Solid Object." (U.S. Patent Application 08/046,245, submitted and approval pending).

        Cox, James; Karron, Daniel; and Mishra, B. "The SpiderWeb Surface rendering algorithm." Innovation and Technology in Biology and Medicine. 14(6) 634-655, December 1993.

        Karron, Daniel; Lu, Zhong-Lin; Williamson, Samuel J. "Pointer: An accurate method for registering anatomical and functional images of the head." (in preparation)

        Karron, Daniel. "Novel surface rendering and object registration methods for three-dimensional medical imaging: The ‘SpiderWeb’ surface algorithm and the ‘pointers’ technique for integrating multimodal images. Ph.D. dissertation.

        Karron, Daniel and Cox, James. "Mathematical Analysis of ‘SpiderWeb’ surface construction algorithm. Proceedings of the 14th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. J.P. Morucci, R. Plonsey, J. L. Coatrieux, and S. Laxminarayan, Editors. 1993: pp. 2084-2086.

        Karron, Daniel. "The ‘SpiderWeb’ algorithm for surface construction in noisy volume data." New York University Department of Robotics, Technical Report, 1992.

        Cox, James; Karron, Daniel; and Mishra, Bud. "The ‘SpiderWeb’ surface construction algorithm for medical imaging: properties of its surface." City University of New York, Brooklyn College Computer Science Department Technical Report, 1992.

        Williamson, Samuel J.; Lu, Zhong-Lin; Karron, Daniel; and Kaufman, Lloyd. "Advantages and limitations of magnetic source imaging." Brain Topography (4)2: 169-180, 1991.

        Cutting, Court B., McCarthy, Joseph G., and Karron, Daniel B. "three-dimensional input of body surface data using a laser light scanner." Annals of Plastic Surgery, 21(1): 38-45, July 1988.

      2. Invited Lectures

      1. Employment History

      1. Professional Memberships

        2. American Association for the Advancement of Science (AAAS), Member since 1976

        American Institute of Physics (AIP)

        American Association of Physicists in Medicine (AAPM)

        Biometrics Society

        Association for the Advancement of Medical Instrumentation (AAMI)

        American Institute of Ultrasound in Medicine (AIUM)

        Association for Computing Machinery (ACM). ACM Special Interest Group for Graphics (SIGGRAPH)

        Institute of Electrical and Electronic Engineers (IEEE)

        Engineering in Medicine and Biology Society (EMBS)

        IEEE Societies:

        Nuclear and Plasma Sciences Society,

        Magnetics Society,

        Signal Processing Society,

        Computer Society.

        American Mathematical Association (AMS)

        Mathematical Association of America (MAA)

        New York Academy of Science (NYAS)

        Society for Magnetic Resonance (SMR)

        Society for Computer Applications in Radiology (SCAR)

        The Society for Imaging Science and Technology (IS&T)

        The International Society for Optical Engineering (SPIE)

        The Society of the Sigma Xi

        The C Users Group (CUG)

        TEX Users Group (TUG)

        NYC Chapter of the X Users group (NYCXUG), Chapter Secretary.

      2. Other Professional Affiliations

        3. Editorial Board Member, Journal of Medicine and Virtual Reality

        American Museum of Natural History, Department of Vertebrate Paleontology (Volunteer Visiting Scientist, software developer of "TableTop" 3D Digitizing System used to make 3D models of fossils).

        Listed in Who’s Who, and American Men and Women of Science.

      3. Professional References

        4. Dr. Bud Mishra, New York University, Department of Robotics

        Dr. Samuel J. Williamson, New York University, Center for Neural Science

        Dr. Edgar E. Coons, New York University, Department of Psychology

        Dr. Eugene A. Grossi, New York University Medical Center, Department of Surgery

      4. Contract Proposals, Funded, Accepted and Funding Pending