• Problem subdomain
• Image descriptors and approaches
• Why fractals?
• Our method

  • Background
  • Least square minimization
  • Central theorem

• Summary and future work

• Given a library of reference images: I₁, I₂, ..., I_n, and a query image Q

  • Preprocess reference images to produce indices
  • Find closest image P to Q
  • Find near matches to Q
  • Objects in Q may not be taken in the same orientation or lighting conditions

• Want to handle objects such as faces, pictures of trees, crumpled newspapers
• Difficult to model object in detail
  
  
  Figure 1: A range of images.

• Robust, automatic, fast methods
• Formal basis

Our current results are preliminary, and on gray level images

• Histograms and signatures
• Range and nearest-neighbor searches
• k-d trees

  • O(n) storage, O(n logn) construction time
  • O(n^1-1/d + k) query time (upper bound)

• Range trees

  • O(n log^d-1n) storage and construction time
  • O(log^d n + k) query time

• Approximate k nearest neigbours
• Large constants in search solutions
• Dimension of space is large

• Consider a ``range'' search on the frame area
  
  
  Figure 3: Frame border of width e.

• Ratio of frame area to the overall space

  • In two dimensions, [(r²- (r - e)²)/(r²)]
  • In d dimensions, [(r^d- (r - e)^d)/(r^d)]
  • Limit, as d becomes large is 1
  • Too many neigbours
  • It is more efficient to simply scan all points (lose advantages of indexing)

• Modeling images
• Fractal Image Compression provides evidence that you can have short image descriptors
• More subtle: A way of dividing an image into regions

• The ``computer-friendly'' way
  
  
  Figure 4: What happens if image changes slightly?

• An oracle segmentation
  
  
  Figure 5: Good segmentation

• Domains & Ranges
• Produces a signature
• Quantifiable errors (similar to the big-Oh sense)

• Setting for the number of copies
• Setting for position, scaling stretching, skewing and rotation for each copy

• Few parameters produce complex images

  a	b	c	d	e	f	yshift
  0.00	0.00	0.00	0.16	0.00	0.00	0
  0.85	0.04	-0.04	0.85	0.00	1.60	40
  0.20	-0.26	0.23	0.22	0.00	1.60	40
  -0.15	0.28	0.26	0.24	0.00	1.40	11

• Parameters define IFS

  • Affine, e.g., w₂: (x,y) = (0.85x + 0.04y, -0.04x + 0.85y + 40)
  • Contractive: f:² ® ²: $s such that d(f(x), f(y) £ s d(x,y) for all x, y in ²
  • IFS: A collection of contractive affine transforms

• IFS result in a fixed point (thus, a signature)

Parameters behave ``nicely''

Theorem 1 Let (P, d_p) and (X, d) be metric spaces, the latter being complete. Let w: P ×X ® X be a family of contraction mappings on X with contractivity factor 0 £ s < 1. That is, for each p Î P, w(p, .) is a contraction mapping on X. For each fixed x Î X, let w be continuous on p. Then the fixed point of w depends continuously on p. That is x_f: P® X is continuous

• Given an image, generate an IFS
• So called ``Collage theorem'' gives a handle on this

Theorem 2 Let (X, d) be a complete metric space. Let f: X ® X be a contraction mapping with contractivity factor 0 £ s £ 1, and let the fixed point of f be x_f Î X. Then

• Natural images are not self-similar
• Look for region-wise self similarity
• Partitioned IFS have properties similar to IFS
• Fixed points of PIFS approximate the image (that's one reason why fractal image compression is lossy)

• Setting for the number of copies
• Setting for position, scaling stretching, skewing and rotation for each copy
• A contrast and brightness adjustment for each copy
• A mask that selects, for each copy, a portion of the image
• Mathematical analog
  So what does the PIFS code look like?

  Ri	D(x)	D(y)	oi	ismti
  R1	x1	y1	o1	ismt1
  ·	·	·	·	·
  ·	·	·	·	·
  Rn	xn	yn	on	ismtn

  Table 1: Template of the PIFS code for an image.
  Example

  Ri	D(x)	D(y)	oi	ismti	Ri	D(x)	D(y)	oi	ismti
  1	15	8	-11	0	2	1	5	33	2
  3	3	11	40	5	4	16	4	29	0
  5	0	4	0	7	6	0	6	36	4
  7	0	2	26	4	8	11	11	8	4
  9	0	3	-05	6	10	3	11	28	0
  11	0	6	41	2	12	14	11	15	5
  13	0	4	-13	5	14	4	6	14	7
  15	3	6	22	4	16	0	10	-15	7

  Table 2: PIFS code for grayscale Lena.
  
  
  Figure 9: Evolving Lena
  How to find parameters?
  • Geometric part v_i found by using various domains, and looking for isometries
  • Scaling and brightness parts found by using least square minimization

    • Given two squares containing n pixel intensities a₁, a₂, ..., a_n and b₁, b₂, ... b_n.
    • Find s and o to minimize the quantity

      Si = 1n (sai + o - bi)2

  The inverse problem
  • Can we use PIFS for indexing?
  • Unfortunately, PIFS are not unique
  • Counterexample: A rectangle

    • Four squares half the size
    • Three rectangles, appropriately positioned
    
    
    Figure 10: Two IFS codes for same fixed point

  Canonical PIFS: Central result
  • Given two images A and B which are close together

    • There exists two canonical PIFS W1 and W2
    • Fixed point of W1 is close to A
    • Fixed point of W2 is close to B
    • Distance between W1 and W2 in parametric space is close

  • Proof ideas:

    • Induction, Triangle inequality, Lispchitz condition
    • If a set of points define a least squares line, then changing one point slightly does not change the line too much.

  Basic algorithm
  • Given a library of reference images: I₁, I₂, ..., I_n
  • Generate PIFS code using any FIC algorithm for image I₁
  • ``Deform'' the PIFS to generate a PIFS code for I₂ with some collage error
  • Produce PIFS codes for other images I₃, I₄, ... I_n
  • Loop to produce codes so that the collage error is the smallest
  • Given a query image Q, produce a PIFS code q by the same deformation process
  • Compare the distance between q and other descriptors using any standard technique
  Sample images
  
  
  Figure 11: CSE department faculty rogue gallery
  Sample images
  
  
  Figure 12: Rotated, scaled fern
  
  
  Figure 13: Rotated cutter
  Sample images
  
  
  Figure 14: Common household objects
  Summary
  • Fractal descriptors are compact and can model a variety of images
  • PIFS is a way of content-based partition of images
  • PIFS are not unique
  • Canonical PIFS can be used for object indexing
  Future work
  • Lots!
  • Provide a robust web-based prototype
  • Use better similarity measures
  • Use different deformations (other than least squares)
  • Compare against other methods
  • Integrate with existing methods

  ---

  File translated from T_EX by T_TH, version 2.34.
  On 11 Sep 1999, 13:53.