Browse Prior Art Database

Method for SIMD fractal image encoding based on a hierarchical correlation between range blocks and domain blocks

IP.com Disclosure Number: IPCOM000008006D
Publication Date: 2002-May-10
Document File: 5 page(s) / 116K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for single instruction stream, multiple data stream (SIMD) fractal image encoding based on a hierarchical correlation between range blocks and domain blocks. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Method for SIMD fractal image encoding based on a hierarchical correlation between range blocks and domain blocks

Disclosed is a method for single instruction stream, multiple data stream (SIMD) fractal image encoding based on a hierarchical correlation between range blocks and domain blocks. Benefits include improved performance.

Description

              Disclosed is a method for encoding fractal images based on a hierarchical correlation between range blocks and domain blocks.

              Fractal image coding is a method for compressing images. A memory footprint is created for an image, enabling recreation of the image with minimal accuracy loss.

              A database of two types of blocks is required. The division of the image into equal squares that do not overlap is the range blocks database (RBD). The division of the image into overlapping, equal, double-sized squares is called the domain blocks database (DBD, see Figure 1).

              Every range block in the RBD is matched to its most suitable domain block from the DBD. During matching, the block’s contrast may be changed by multiplying it by a constant value. The block’s offset may be changed by adding a constant value. The constant that is being multiplied by the domain block’s contrast, the constant that is being added to the offset, and the block number are the transformation parameters of the range block. Compression is achieved when, instead of coding the pixels of the image, only the transformation’s parameters are coded.

Fractal image encoding algorithm based on hierarchy

              The fractal image encoding algorithm based on hierarchy performs the following processing steps:

1.      Divide the image into equal blocks that do not overlap (N), where each block size is
B X B, and B is an integer power of 2. This partition is called the range blocks database.

2.      Divide the same image into overlapping equal blocks (M), where each block size is
2B X 2B, shifted at steps size B in each axis, where B is the same as in step 1. This partition is called the domain blocks database.

3.      For each range block, a full search on the entire DBD is performed to reach the minimum mean square error (MSE). That is, find  and  for each (see Figure 2). To minimize the MSE, the DBD resolution is reduced from 2B X 2B to B X B by averaging every 4 neighbor pixels into 1 pixel. Then the expression is evaluated. ( denotes the  domain block after reducing its resolution.) If the MSE exceeds a specified threshold, then divide the range block sized B X B into four non-overlapping range blocks sized ½B X ½B, and repeat step 3. This recursive procedure constructs a quad-tree structure, which is also encoded.

4.      The parameters , and j are encoded and are declared the fractal code . Instead of coding the pixels of the image, only the transformations’ parameters are required to be coded and compression i...