A New Simulation of Spiral Architecture

No comments

Introduction

Hexagonal structure is different from the traditional square structure for image representation. The geometrical arrangement of pixels on hexagonal structure can be described in terms of a hexagonal grid. Hexagonal structure provides an easy way for image translation and rotation information. Spiral Architecture is a relatively new and powerful approach to machine vision system. However, all the existing hardware for capturing image and for displaying image are produced based on rectangular architecture. It has become a serious problem affecting the advanced research on Spiral Architecture. In this paper, a new approach to Spiral Architecture is presented using MATLAB. This mimic Spiral Architecture almost retains image resolution and does not introduce distortion. Furthermore, images can be smoothly and easily transferred between the traditional square structure and this new hexagonal structure.

Overview of Hexagonal Grid

A digital image contains thousands of pixels to represent the real world and when we touch the term ‘pixel’ so far, that means a rectangular box in an image. Almost all the previous image processing and image analysis research is based on this traditional image structure. The advantages of using a hexagonal grid to represent digit images have been investigated for more than thirty years. The importance of the hexagonal representation is that it possesses special computational features that are pertinent to the vision process. Dozens of reports describing the advantages of using such a grid type have been found in the literature. The hexagonal image structure has features of higher degree of circular symmetry, uniform connectivity, greater angular resolution, and a reduced need of storage and computation in image processing operations. Its computational power for intelligent vision pushes forward the image processing field consists of the organizational units of vision. In spite of its numerous advantages, hexagonal grid has so far not yet been widely used in computer vision and graphics field. The main problem that limits the use of hexagonal image structure is believed due to lack of hardware for capturing and displaying hexagonal-based images. In hexagonal grid each unit is a set of seven hexagons compared with the traditional rectangular image architecture using a set of 3× 3 vision unit as shown in Figure 1. On a hexagonal image structure, each pixel has only six neighbouring pixels which have the same distance to the central pixel. In this report, we will construct a hexagonal structure that is converted from the traditional square structure easily and quickly using MATLAB

pic1Figure 1. Unit of vision in two image architectures

Virtual Hexagonal Structure

Using virtual Spiral Architecture, images on rectangular structure can be smoothly converted to Spiral Architecture. The Virtual Spiral Architecture exists only during the procedure of image processing. Finally, the resulted data can be mapped back to rectangular architecture for display as shown in Figure 2. The main disadvantage of using this approach is that the computation cost is high when converting between the square based images and hexagon based images.

simFigure 2. Image processing on virtual Spiral Architecture

Spiral Addressing

Unlike the square lattice, the points in a hexagonal lattice do not easily lend themselves to be addressed by integer Cartesian coordinates. This is because the points are not aligned in two orthogonal directions. Apparently, the hexagonal pixels cannot be labelled in row and column order as in the traditional rectangular structure. In order to properly address and store hexagonal images data, Sheridan proposed a one-dimensional addressing scheme for a hexagonal structure. The first step in Spiral Addressing formulation is initially labelling each of the individual hexagons with a unique address. The addresses of these hexagons will then be simply referred to as the hexagons. This is achieved by a process that is initially applied to a collection of seven hexagons. Each of these seven hexagons is labelled consecutively with addresses 0, 1, 2, 3, 4, 5 and 6 as displayed in Figure 3.

pic3Figure 3. A collection of seven hexagons with unique addresses

Dilate the structure so that six additional collections of seven hexagons can be placed about the addressed hexagons, and multiply each address by 10. For each new collection of seven hexagons, label each of the hexagons consecutively from the centre address as we did for the first seven hexagons. The repetition of the above steps permits the collection of hexagons to grow in powers of seven with uniquely assigned addresses. It is this pattern of growth of addresses that generates the Spiral as illustrated in Figure 4.

SAFigure 4. Spiral Architecture with spiral addressing

The addresses are consecutive in base seven. MATLAB functions dec2hept and hept2dec are used to convert between base 7 and decimal numbers. The important aspect of each hexagon is that it has six neighbouring hexagons. This establishes the property that for all hexagons, the centre of each hexagon has a constant distance from every one of its six neighbours.

For the whole image, following the spiral rotation direction, as shown in Figure 4, one can find out the location of any hexagonal pixel with a given spiral address starting from the central pixel of address 0. From Figure 4, it is easy to see that finding neighbouring pixels plays a very important role to locate a pixel and hence is critical in the process of the two operations defined on the SA. The location of the pixel with a given spiral address

eq1can be found from the locations of

eq2For example, to find the location of the pixel with spiral address 43, we need only know the locations of the pixels with spiral addresses 40 and 3.

Construction of Hexagonal Pixels

To construct hexagonal pixels, each square pixel is first separated into 7×7 smaller pixels, called sub-pixels. To be simple, the light intensity for each of these sub-pixels is set to be the same as that of the pixel from which the sub-pixels are separated. Each virtual hexagonal pixel is formed by 56 sub-pixels arranged as shown in Figure 5. To be simple, the light intensity of each constructed hexagonal pixel is computed as the average of the intensities of the 56 sub-pixels forming the hexagonal pixel. A hexagonal pixel, called a hyperpel, is simulated using a set of many square pixels. The MATLAB function hypel is used to simulate a hexagonal pixel on a square grid according to Figure 5.

pic2Figure 5. The structure of a single hexagonal pixel

Note that the size of each constructed pixel is

eq2.5bigger than each square pixel. Hence, the number of hexagonal pixels is 12.5% less than the number of square pixels to cover the same image. Because of this percentage, the hexagonal pixels constructed in the way above will not lose image resolution if proper light intensities of hexagonal pixels are assigned or interpolated.

Simulation of Spiral Architecture

Figure 6 shows a collection of seven hexagonal pixels constructed with spiral addresses from 0 to 6.

pic4Figure 6. A cluster of seven hexagonal pixels

From Figure 6, it is easy to see that the hexagonal pixels constructed in this way tile the whole plane without spaces and overlaps. From Figure 6, it can be easily computed that the distance from pixel 0 to pixel 1 or pixel 4 is 8. The distance from pixel 0 to pixel 2, pixel 3, pixel 5 or pixel 6 is

eq7This is close to 8. Hence, the feature of equal distance is almost retained and hence this construction hardly introduces image distortion.

Locating Hexagonal Pixels

To simulate spiral architecture, we only need to derive the way to locate the pixel with spiral address in the form of

eq3Let us use vector [0 0] to denote the location of the hexagonal with spiral address 0, and vector [j k] (j, k are integers) to denote the location of a pixel that is obtained by moving from [0 0] down (or up if j is negative) for |j| sub-pixels and towards right (or left if k is negative) for |k| sub-pixels and. If we also use L(a) to denote the location of the hexagonal pixel with spiral address a, then we have L(0) = [0 0]. From Figure 6, it is easy to see that

L(1) = [8 0], L(2) = [4 -7], L(3) = [-4 -7], L(4) = [-8 0], L(5) = [-4 7] and L(6) = [4 7]

The location of hexagonal pixel with address 10 is obtained by moving from pixel 1 in the direction from pixel 6 towards pixel 1 for two pixels distance. The MATLAB function spl_shift is used to calculate the shift from the pixel with 0 spiral address. The shift for addresses 0 to 6 are base cases for the recursive algorithm. The algorithm for multiples of 10 is given by.

eq4While the location of the pixel with a given spiral address

eq5can be computed by

eq6MATLAB Simulation of Spiral Architecture

MATLAB functions sprl2rect is used to simulate a hexagonal image represented in spiral addressing scheme. Figures 7 to 9 are MATLAB images of hexagonal images given as one dimensional array. The MATLAB script is given at the end.

fig07Figure 7. A cluster of 7 hexagonal pixels

fig08

Figure 8. A cluster of 7^2 = 49 hexagonal pixels
fig09Figure 9. A cluster of 7^3 = 243 hexagonal pixels

The Figure 10 shows a simple conversion of an image from rectangular architecture to spiral architecture. More complex examples are not considered due to high computation power requirement. The MATLAB script is given at the end.

r2sFigure 10. A simple conversion from rectangular to spiral architecture

Conclusion

In this report, a novel method to construct or mimic the Spiral Architecture has been implemented in MATLAB. This constructed hexagonal structure does not change the image resolution and introduce image distortion. It retains the advantages of the real hexagonal system such as higher degree of symmetry, uniformly connected and closed-packed form. This structure together with the light intensities cannot be displayed and it exists only in the computer memory during the procedure of image processing. Image processing based on a hexagonal structure can be implemented using this structure. The construction of this new mimic structure does not require complex computation for determining the regions of hexagonal pixels, and does not require to build a large table stored in the computer memory to record the pixel locations. The location of each pixel can be easily and quickly determined and computed using mathematical formulae.

MATLAB Code

function mat = hypel( mat, row, col, val )
%HYPEL Returns hexagonal pixels

mat(row:row + 7, col:col + 4) = val;
mat(row + 1:row + 6, col - 1) = val;
mat(row + 1:row + 6, col + 5) = val;
mat(row + 3:row + 4, col - 2) = val;
mat(row + 3:row + 4, col + 6) = val;
function dec = hept2dec(num)
%HEPT2DEC Converts base 7 number into decimal number

len = length(num2str(num)) - 1;
 
dec = 0;
 
for n = len:-1:0
    digit = fix(num / 10 ^ n);
    dec = dec + digit * 7 ^ n;
    num = mod(num, 10 ^ n);
end 
function hept = dec2hept(num)
%DEC2HEPT Converts decimal number into a base 7 number.
 
hept = 0;
temp = fix(num/7);
r = mod(num,7);
exp = 0;
 
while temp ~= 0;
    hept = hept + r * 10 ^ exp;
    r = mod(temp,7);
    exp = exp + 1;
    temp = fix(temp/7);
end
 
hept = hept + r * 10 ^ exp;
function sft = spl_shift( address )
%SPL_SHIFT Returns the horizontal and vertical shift as a 2 %element row vector.
%The address must be a base 7 number. 
 
if address == 0
    sft = [0 0];
elseif address == 1
    sft = [8 0];
elseif address == 2
    sft = [4 -7];
elseif address == 3
    sft = [-4 -7];
elseif address == 4
    sft = [-8 0];
elseif address == 5
    sft = [-4 7];
elseif address == 6
    sft = [4 7];
    
elseif mod(address,10) == 0
    len = length(num2str(address));
       
    for n = (len - 1):-1:1
        digit = fix(address / 10 ^ n);
        if digit == 0
            break
        elseif digit ~= 6
            sft = spl_shift(digit * 10 ^ (n - 1)) + ...
                2 * spl_shift((digit + 1) * 10 ^ (n - 1));
        else
            sft = spl_shift(6 * 10 ^(n - 1)) + 2 * ...
                spl_shift(10 ^ (n-1));
        end
        address = mod(address, 10 ^ n);
    end
    
else
    len = length(num2str(address))-1;
    sft = [0 0];
    
    for n = len:-1:0
        digit = fix(address / 10 ^ n);
        if digit ~= 0
            sft = sft + spl_shift(digit * 10 ^ n);
        end
        address = mod(address, 10 ^ n);
    end
end
function rect = sprl2rect( sprl )
%SPRL2RECT Converts SA into Rectangular for display.

len = length(sprl);
rad = ceil(log(len)/log(7));
size = ceil(8.06 * (3 ^ rad));
cent = fix(size / 2);
rect = uint8(zeros(size));
start = [cent cent];
for i = 0:(len - 1)
    spl_address = dec2hept(i);
    coord = start + spl_shift(spl_address);
    rect = hypel(rect,coord(1),coord(2),sprl(i+1));
end
% Sample script to display an image of spiral architecture.

image(1:7) = 80;
image(8:49) = 120;
image(50:7^3) = 180;
image(7^3+1:7^4) = 220;
sqgrd = sprl2rect(image);
imview(sqgrd);
% Sample script to convert a 3 x 3 image from rectangular % to spiral architecture.
im = uint8([120 120 120;120 20 120;120 120 120]);
new = imresize(im, 8, 'nearest');
subplot(121);imshow(new),title('Rectangular');
start = [9 10];
for i = 0:6
   coord = start + spl_shift(dec2hept(i));
   row = coord(1);
   col = coord(2);
   val = (sum(sum(new(row:row + 7, col:col + 4))) + ...
          sum(new(row + 1:row + 6, col - 1)) + ... 
          sum(new(row + 1:row + 6, col + 5)) + ... 
          sum(new(row + 3:row + 4, col - 2)) + ... 
          sum(new(row + 3:row + 4, col + 6))) / 56;
          spr(i+1) = uint8(val);
end
sqrgrd = sprl2rect(spr);
subplot(122);
imshow(sqrgrd),title('Spiral');

Resources

  • Xiangjian He, Wenjing Jia, Qiang Wu, Namho Hur, Tom Hintz, Huaqing Wang and Jinwoong Kim, ” Basic Transformations on Virtual Hexagonal Structure”, Proceedings of the international conference on Computer Graphics, Imaging and Visualization, 2006.
  • H. Wang, M. Wang, T. Hintz, et al., “VSA-based Fractal Image Compression, Journal of WSCG”, 2005.
  • Xiangjian He, Tom Hintz, Qiang Wu, Huaqing Wang and Wenjing Jia, “A New Simulation of Spiral Architecture” Proc. of International Conference on Image Processing, Computer Vision, and Pattern Recognition, 2006.
  • P. Sheridan, T. Hintz, and D. Alexander, “Pseudo-invariant Image Transformations on a Hexagonal Lattice,” Image and Vision Computing, 2000.
  • Lee Middleton and Jayanthi Sivaswamy, “Hexagonal Image Processing: A Practical Approach” Springer-Verlag London Limited, 2005.
  • This is the web version of the project report in the subject Digital Image Processing that I took in College of EME. You can download Word document from here. You can download associated paper from here and PowerPoint presentation from here.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s