From: rick@cs.arizona.edu (Rick Schlichting)
Newsgroups: comp.research.japan
Subject: Kahaner Report: Audio & Visual Info Res Group Seminar, Tokyo, 9/92
Date: 27 Sep 92 03:38:20 GMT


  [Dr. David Kahaner is a numerical analyst on sabbatical to the 
   Office of Naval Research-Asia (ONR Asia) in Tokyo from NIST.  The 
   following is the professional opinion of David Kahaner and in no 
   way has the blessing of the US Government or any agency of it.  All 
   information is dated and of limited life time.  This disclaimer should 
   be noted on ANY attribution.]

  [Copies of previous reports written by Kahaner can be obtained using
   anonymous FTP from host cs.arizona.edu, directory japan/kahaner.reports.]

To: Distribution
From: 
 David K. Kahaner
 US Office of Naval Research Asia
 (From outside US):  23-17, 7-chome, Roppongi, Minato-ku, Tokyo 106 Japan
 (From within  US):  Unit 45002, APO AP 96337-0007
  Tel: +81 3 3401-8924, Fax: +81 3 3403-9670
  Email: kahaner@cs.titech.ac.jp
Re: Audio and Visual Information Research Group (AVIRG) Seminar, Tokyo, 9/92
21 Sept 1992
This file is named "avirg.92"

ABSTRACT. Summary of two lectures on image reproduction presented at the
Audio and Visual Information Research Group Seminar, held at University
of Tokyo, 3 Sept 1992. (M. Kobayashi)


This report is received, with thanks, from
        Dr. Mei Kobayashi
        IBM Japan Ltd
        5-19 Sanbancho Chiyoda-ku Tokyo 102 Japan
         Tel: 81+3-3228-8287, Fax: 81+3-3265-4251
         Email: MEI@TRLVM.VNET.IBM.COM

AVIRG (Audio and Visual Information Research Group) Seminar

Date: Sept 3, 1992 (Thursday)
Location: Dept. Eng., U. Tokyo (Hongo Campus), Bldg. 6, 2F Room 63
Topic: "Reproduction of Images"

Schedule:
 1. Reproduction of CT images by FFT           14:00 - 15:30
          M. Tabei (Tokyo Institute of Technology)

 2. Image restoration by blind deconvolution   15:30 - 17:00
          S. Komatsu (Waseda Univ.)

Talk 1: (Tabei)
The first talk described how FFT may be used for generation of Computer 
Tomography Images (CT). The speaker gave three references at the start
of his talk, and indicated that ideas presented in the talk are not
entirely new.

  References:
  1. Jain, "Fundamentals of Digital Image Processing" (book)
  2. Denshi-tsu-shin Gakkai D-II No.2, pp. 237-246(1989)
     by Niki Noboru ( or Futaki Noboru ) in Japanese
  3. J.D. O'Sullivan, No. 4 (1985) IEEE Trans. Med. Imag. Process.

Unfortunately, my background in CT is very poor so I am able to give only 
a very short, rough summary. The speaker focused on two specific tasks 
necessary for solving the imaging problem 
  1. accurate conversion between polar coordinates and rectangular
     coordinates
  2. accurate conversion of data near the center or origin.

Because CT data is gathered from projections from a series of angles, 
polar-coordinate-type data cannot be simply converted to a rectangular 
system by strightforward surperposition; a special Jacobian or filter is 
needed. Background noise and blurring also contribute to the difficulty 
of the problem. In particular, the origin seems to be a difficult spot, 
and the speaker described a new type of filter he developed to overcome 
the problem.  He showed many examples of successful reconstruction using 
the filter with supporting error analysis. The main conclusion was that 
equal or better results could be achieved in 1/5 of the computation time 
for 512x512 images and 1/10 for 1024x1024 by using this modified FFT 
method rather than the conventionally accepted backprojection method.  

Talk 2: (Komatsu)
The second talk described a simple iterative algorithm for deblurring of
2-dimensional images. The speaker gave the following outline for his
talk:

1. Blind Deconvolution (Intro)
   - Principles
   - Necessity/Significance
   - Relationship with Other Methods
2. Algorithms
   - Homomorphic Filter
   - Zero Sheet(s)
   - Fourier
3. FFT Iterative Transform Algorithm
   - Applications to Deblurring of 2-D Photographic Images
   - Applications to Deblurring of Stellar Telescope Data

Komatsu intriduced himself as a hikari (light or optics) specialist with
only limited experience in image and signal processing.  The iterative
transform algorithm was first applied to sharpen reuslts from simulation
studies, and he was at first skeptical that it could be extended to
deblur real images. He viewed the algorithm as a method for solving an
inverse problem: given a blurred image, determine the original unblurred
image. Many deblurring algortihms have been proposed however three were
discussed:

  1. Homomorphic Filter - Stockham (1975)
  2. Zero Sheet(s) - Lane and Bates (1987)
  3. Iterative Transform Algorithm - Ayers and Dainty (1988)

The Homomorphic Filter assumes that the blurred portion of an image is
very small i.e., a perturbation, compared to the overall picture.

      C      =     F     *         G
    given       original          blur

    log |C|  =  log |F|    +     log|G|

There is also a problem associated with unique determination of the
angle associated with the log function since an arctan term appears.

The Zero Sheet method cannot be applied to the 1-dimensional problem
since a "sheet" in 1-D space is a point. The 2-D problem is described
below. The Discrete Fourier Transform (DFT) of a function f sampled at
f(m,n) is decsribed by ( in TeX notation ):

      F(u,v) = \sum _m \sum _n f(m,n) e^{i(mu+nv)\Omega }
let:  \xi = e^{iu\Omega }    and    \psi = e^{iv\Omega }
then: F(\xi ,\psi ) = \sum _m \sum _n f(m,n) \xi ^m \psi ^n

We call the surface described by:  F(\xi ,\psi ) = 0 , a Zero Sheet.
For all practical purposes, when applying this technique to real image
problems, there is only one zero sheet, although mathematical
counterexamples can be easily constructed. Convolutions have two Zero
Sheets ( for all practical purposes ) since:
         C(\xi ,\psi ) = F(\xi ,\psi ) G(\xi ,\psi )
the idea is to compute the zero sheets and seperate them. Unfortunately
the method has two major drawbacks:
  1. It is VERY computationally intensive.
  2. It is very sensitive to noise.
so that it cannot be applied to large images
 
The Fourier Iterative Transform Algorithm in described in the references
below. Theoretical aspects of the algorithm are not entirely clear; it
is just found to be good in practice. The algorithm consists of 3 main
steps: inverse filtering, image constraints, and apodization filters.
Komatsu showed examples on how an initial "guess" image congerges to an
unblurred image in a random zig-zag way. It may take over 100 iterations
to come up with a good picture, with no way to guess when a bad or good
image will appear. To speed up the process, two intermediate results may
be combined.

The final example was from an image of 2 stars taken from a telescope.
Because they appear very close to each other, it is difficult to tell
that there are two until the deblurring scheme is applied. A cute, but
nevertheless, interesting result. For the moment, Komatsu admits that
the method appears to be just that - a cute toy for scientists.
Hopefully a better theoretical understanding will be developed to
further improve the algorithm to make it a very useful tool and standard
technique.

  References:
  1. S. Komatsu, J.C. Dainty, Appl. Opt. Digest 295-296 (1990)
  2. G.R. Ayers and J.C. Dainty, Opt. Lett. 13, 547 (1988)

I noticed that the organizer (Takao Kobayashi) made a tape of the talks 
as well as the Q & A sessions, however I do not know whether it is 
available to the public.  The second speaker, Komatsu, said he just 
returned from a stay in England so it is safe to assume that he can 
communicate in English. When writing to Kobayashi, I recommend writng the 
full first name since there are usually at least a few Kobayashis in 
every department (always a source of great confusion for me and my 
colleagues). For further information, please contact: 

S1:  M. Tabei
     Semetsu (Precision) Engineering Department
     Tokyo Institute of Technology
     4259 Nagatsuda-cho Midori-ku, Yokohama-shi 227 Japan

S2:  S. Komatsu
     Engineering, Waseda Univ.
     3-4-1 Okubo, Shinjuku-ku Tokyo 169 Japan

     J.C. Dainty
     Optics Section, The Blackett Laboratory, Imperial College
     Prince Consort Road, London SW7 2BZ England

Organizer: Takao Kobayashi
     Semetsu (Precision) Engineering Department
     Tokyo Institute of Technology
     4259 Nagatsuda-cho Midori-ku, Yokohama-shi 227 Japan
      Tel: +81 45-9222-1111 ext. 2030; Fax: +81 45-921-0898
      Email: TKOBAYAS@PI.TITECH.AC.JP

------------------------------END OF REPORT------------------------------