Table of Contents

Dedication

Preface

Book Organization

FIRST PART: Mojette Theory

Chapter 1: Discrete Geometry and Projections

1.1. Introduction

1.2. Discrete pavings and discrete grids

1.3. Topological principles and discrete objects

1.4. Arithmetic principles

1.5. Discrete geometry elements

1.6. Conclusion

1.7. Bibliography

Chapter 2: Discrete Versions of the Radon Transform

2.1. Introduction

2.2. General linear Radon transform

2.3. Discrete versions of the Radon transform

2.4. Katz geometry

2.5. Conclusion

2.6. Bibliography

Chapter 3: Direct Mojette Transform

3.1. Introduction

3.2. Computing Mojette projections

3.3. Properties

3.4. Alternative pixel model

3.5. Mojette transform in higher dimensions

3.6. Conclusion

3.7. Bibliography

Chapter 4: Reconstructability with the Inverse Mojette Transform

4.1. Introduction

4.2. The reconstructabiity of convex regions

4.3. The choice of optimum angle sets

4.4. Exact filtered backprojection reconstruction

4.5. The notion of phantoms and partial reconstructabiity

4.6. Reconstructability in higher dimensions

4.7. Conclusion

4.8. Bibliography

Chapter 5: Inverse Mojette Transform Algorithms

5.1. Introduction

5.2. Iterative local reconstruction (ILR)

5.3. Geometry-driven reconstruction (GDR)

5.4. Global Mojette reconstruction

5.5. Mojette inversion using the FRT

5.6. Conclusion

5.7. Bibliography

Chapter 6: Multiresolution Mojette Transform

6.1. Introduction

6.2. Scalable Mojette projections

6.3. Progressive reconstruction

6.4. Reconstruction of lossy or noisy scalable projections

6.5. Shear-stack Mojette projections

6.6. Multiresolutional shear-stack Mojette projections

6.7. Reconstruction from multiresolution projections

6.8. Conclusion

6.9. Bibliography

SECOND PART: Applications

Chapter 7: Communication, Networks and Storage

7.1. Introduction

7.2. Mojette coding: a geometric channel coding

7.3. Applications in communication and storage

7.4. Priority encoding transmission

7.5. Conclusion

7.6. Bibliography

Chapter 8: Mojette Discrete Tomography

8.1. Introduction

8.2. Operators

8.3. Mojette operators in classic tomography algorithms

8.4. Discussion

8.5. Conclusion

8.6. Bibliography

Chapter 9: Lossless Compression

9.1. Introduction

9.2. A review of the preliminary study

9.3. Projection compression using multichannel audio techniques

9.4. Projection compression using multiband image techniques

9.5. Conclusions

9.6. Bibliography

Chapter 10: Mojette-based Security

10.1. Introduction

10.2. Digital watermarking

10.3. Shared secret

10.4. Encryption

10.5. Conclusion

10.6. Bibliography

List of Authors

Index

First published in Great Britain and the United States in 2009 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.iste.co.uk
www.wiley.com

© ISTE Ltd, 2009

The rights of Jean-Pierre Guédon to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

The mojette transform: theory and applications / edited by Jeanpierre Guedon.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-080-6

1. Radon transforms. 2. Geometric tomography. 3. Discrete geometry. I. Guedon, Jeanpierre, 1962-

QA672.M65 2009

515'.723--dc22

2008054465

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-080-6

This book is dedicated to Yves Bizais.

Preface

The last 13 years has seen the nurturing and maturation of a simple but widely useful mathematical tool: the Mojette transform. I wrote the first paper and presented the first talk about this transform in the first semester of the year 1995. That paper reviewed my contribution towards a still unsolved problem in the field of psycho-visual representation. But, as Werner Von Braun said, “basic research is what you are doing when you do not know what you are doing”.

The name Mojette is derived from fields of the rural type; my first mathematical operation was addition that I learnt to perform using beans that are called Mojettes around our territory. The word itself comes from the Middle Ages as Mongette: a bean variety that is still cultivated in Italy (fagioli allocchio nero), Spain (caupi), Portugal (feijão frade), North Africa (lubia), the United States (black-eyed pea or cowpea) and Brazil (feijão de corda). The famous sentence from Lewis Carroll’s Alice in Wonderland, “How many beans make five?” as well as the proverbial wisdom “to count your beans” inspired the naming of the Mojette transform.

This work is inspired by an undeservedly little-known book published in 1978, which summarized the PhD thesis work of Myron B. Katz. Discrete tomography was his topic, as it was for my PhD. Reading his book, while writing lectures for an information theory course, was my starting point for work on a linear transform which had redundancy properties.

Without Nicolas Normand’s early discovery of the strong link between discrete projection operators and the discrete lines used in discrete geometry, the formalism underlying the Mojette transform and the resulting applications would simply not exist. This link transformed a small scientific contribution into an adventure out into the unknown territory of redundancy.

There were different PhD theses, year after year, each finding new theoretical results or developing new applications. Nicolas Normand wrote the first thesis, finding the first fast algorithm for the Mojette inverse transform and being first to prove the theorem that any convex shape could be reconstructed from a set of Mojette projections.

Olivier Philippé exploited the redundancy property to apply this data representation result to network applications and developed the ‘incomplete reconstruction’ theorem. Around the same time, Mark Barratt computed the first algorithm and Dietmar Eggeman introduced the ‘geometric characteristic function’. Benoit Parrein reformulated the latter concept as the ‘geometric buffer’ and demonstrated that the Mojette transform was a useful tool for multiple data descriptions and belonged in the class of error-correcting codes. Pierre Verbert extended results for Mojette into nD, following work by Sandrine LeCoq on the behavior of the transform in 3D. Florent Autrusseau invented diverse schemes for data watermarking that arose through combining psycho-visual and Mojette transform spaces. Myriam Servieres devised several algorithms to apply the Mojette transform for medical computed tomography, i.e. Mojette CT reconstruction using real, noisy x-ray transmission data. By this time, the connection back to the tomographic work I had done with Yves Bizais (on the need for orientation-sensitive filters for backprojection in CT) was very clear. Pierre Evenou developed the concept of distributed data storage in Mojette form and turned it into a commercial reality. Eric Grall formulated cryptographic schemes, based on the Mojette transform, for secure data transmission applications.

Through the Australian connection, with Melbournians Imants Svalbe and Andrew Kingston, we discovered that Mojette had a cousin: the Finite Radon Transform, which shares many similar properties. A collaboration was begun; Andrew’s work on multiresolution Mojette representation, done as a postdoctoral researcher at Nantes, confirmed (if needed) the benefits of working with other teams.

In a similar vein, numerous exchanges of university students with Patrizio Campisi’s team in Italy have occurred over the years. Valuable discussions with people in the discrete geometry community evolved after a meeting organized by Jean-Marc Chassery. In particular, conversations with Alberto Del Lungo and Attila Kuba (both of whom died tragically young, but remain in our thoughts) further extended the depth of the Mojette family through their foundational work on discrete projections. The global spread of Mojette work continues through the increasing number of talented students from China and the Middle East who have come to work at Nantes.

It is a real pleasure to thank people who have made deep contributions, directly or indirectly, to this book. First, to my best friend of more than 20 years, Yves Bizais, I give thanks for sharing with me his delight in life and in conducting research. Second, similar thanks to Bob Wagner (who also passed away recently) who advocated that “life is a test”. Third, thanks to Jean-Marc Chassery for his ardent defence of this transform from receiving a severe pruning when the Mojette seed had just sprouted its first shoots.

Of course, it is my pleasure to thank all the contributors of the following chapters for their patience and agreement to be harnessed to the task of pulling this book through to fruition. A special thanks (again) to Nicolas Normand, who was present from the beginning of this journey and, as the LaTex Tyrant, has wielded the whip-hand over the last months. Thanks also to Nicolas Martin and Aurore Arlicot for spending much time and care on tidying the text to the greater benefit of our readers.

The Image and Video Communications team at Nantes Polytech is warmly thanked for its kind support, especially Nicolas, Benoit, Florent and Pierre (the four mousquetaires), Patrick and Dominque. I also want to thank people from the IRCCyN laboratory, namely Jean-Pierre Elloy, Jean-Francois Lafay and Michel Malabre.

Jeanpierre Guédon

Life is fun. Fun is hard stuff.

Book Organization

At first glance, the book you are reading is organized in a traditional way. The first half of the book presents the Mojette transform with its theoretical results and the second half shows how to use these results to solve real-life problems in imaging and data networks.

Chapter 1 is devoted to discrete geometry. This beginning point is a prerequisite to understanding the discrete character of the transform. In Chapter 2, where some other discrete Radon transforms are presented, a sharp distinction arises for the Mojette case: the ill-posedness of the Radon transform does not disappear, but is subdued by features of the discrete geometry. The first two chapters attempt to explain the balance between the continuous and discrete sides of the transform. Readers more interested in algorithms and properties can skip the first two chapters and return to them when needed. Chapter 3 presents the direct Mojette transform in its different forms and explains the several classes of Mojette transforms that now exist. The strong links between these transforms are exemplified both by the similarity of the algorithms used to compute them and their shared properties. This chapter outlines the necessary tools to compute a set of Mojette projections from any image. Chapter 4 is relevant to the Mojette transform by reviewing how to examine a projection set to determine if it contains sufficient information to permit an exact reconstruction. Various tools for performing the inverse Mojette transform are presented in Chapter 5.

The neologism ‘reconstructability’ (rendered by an electronic spell-checker as ‘reconstruct ability’) has been designed and is applied throughout this book to mean ‘a set of projections for which an algorithm can be created to achieve an exact reconstruction’. This is the core of the Mojette specificity: redundancy appears when we overshoot sufficiency. This overshooting is the key to many applications, but sufficiency is always mandatory to retrieve the original information. Compared to the fixed (1:1) mapping property of the wavelet or Fourier transforms, here the management of redundancy creates the question of maintaining reconstructability; we can choose different combinations or sets of projections to suit any given problem. Chapter 6 presents very new and important results to integrate Mojette and multiresolution data representations. This blending of sampling and scale affects the management of redundancy and the quantization of data into projections.

The second part of the book is devoted to applications of the Mojette transform that have arisen over the last decade. Chapter 7 summarizes, with a brilliant focus, aspects of data storage and data communication. The presentation of ‘geometric channel coding’ as well as ‘geometric buffers’ reconnects the reader to ideas treated in the first chapter. Distributed storage and priority encoded transmission might at first seem to be two distinct properties, but they morph smoothly into each other from the Mojette viewpoint. Chapter 8 reviews inversion algorithms for tomography, in particular for medical applications, where projection noise (and consistency) is a real and significant concern. Chapter 5, by contrast, dealt with inversion from projections where any changes in the data are proscribed (and so could be subtitled ‘noise-free inversion’). The topic of Chapter 9 (lossless compression) may first seem to be oxymoronic, given the Mojette transform creates purposeful redundancy. Nevertheless, the Mojette transform can be used all along the chain of representing, compressing, transmitting and storing data in an efficient manner. Finally, Chapter 10 focuses on presenting just a few of the many published schemes that use Mojette transforms for the encryption and watermarking of data.

I hope the reader experiences a linear revelation that runs parallel to the ideas projected by the authors in this book. But, as the great movie-maker Jean-Luc Godard said: “A movie has a beginning, a middle and an end, but not necessarily in that order”.

Enjoy the Mojette transform through your own chosen path of chapter selection. As you proceed, try to figure out when you have received sufficient information to reconstruct the authors’ intentions as laid out (hopefully with some, but not too much, redundancy) in this book!

FIRST PART

Mojette Theory

Chapter 1

Discrete Geometry and Projections ¹

1.1. Introduction

This book is devoted to a discrete Radon transform named the Mojette transform. The Radon transform specificity is to mix Cartesian and radial views of the plane. However, it is straightforward to obtain a discrete lattice from a Cartesian grid while it is impossible from a standard equiangular radial grid. The only mathematical tool is to use discrete geometry that replaces the equiangular radial line by discrete lines aligned with a pixel grid. This chapter presents and investigates these precious tools.

After having examined the structure of the discrete space in section 1.2, we will focus on topological (section 1.3) and arithmetic (section 1.4) principles that guide the definition of discrete geometry elements (section 1.5).

1.2. Discrete pavings and discrete grids

First of all, let us define the underlying domain: without loss of generality, we can define the discrete space as a tiling P of the plane (or the space in higher dimensions) with non-overlapping enumerable open cells. Hence, a discrete representation of a continuous function f: ² → I is a set of valued

Figure 1.1. Regular grids and regular tilings in two dimensions

cells of P. The function that associates points in ² with cells of P and defines a transfer function for the values I is called a digitization process.

Instead of considering the tiling of cells, we may also consider the dual representation, referred to as the . A cell is represented by a single point (usually its center of gravity) and two points are connected if the two associated closed cells share an edge or a vertex. Such points are called .

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!