com.c3d.image
Class FractalIndex
java.lang.Object

+com.c3d.image.FractalIndex
 public class FractalIndex
 extends java.lang.Object
TeX
The purpose of this class is to provide a fast means of
indexing blocks of 4 pixels, (2x2) blocks, so as to determine
which block of a given larger size is most similar to a particular
block of a smaller size. It is assumed that the blocks being
indexed have been obtained from larger ones by shrinking them.
The operations that are to be allowed in the fractal transform
will be
\begin{enumerate}
\item rotations by 0, 90, 180, 270 degrees
\item contrast adjustment
\item mean brightness offset
\item transfer beween image planes
\end{enumerate}
The index is conceptually a relation with 8 columns as shown
\begin{tabular}{llllllll}
\hline
\multicolumn{4}{c}{Pixels}&rotation&plane&x&y\\
0&1&2&3& & &&\\\hline
30&25&7&9& 2&1&12&205\\
44&90&100&0&3&0&74&103\\
\end{tabular}
Where the rotation indicates the number of clockwise 90 degree rotations
that the set of pixels must undergo to make the 0th pixel the smallest.
The first 5 columns constitute a primary key.
Plane, x and y indicate the origin of the patch in the source image.
The standard numbering of the pixels in the patch is as follows
\begin{tabular}{cc}
\hline
0&1 \\ \hline
3&2 \\ \hline
\end{tabular}
Field Summary 
byte[][][][] 
table
TeX
\subsection*{Internal representation}
Observe that if the pixels are rotated into an orientation such that the
0th pixel is the lowest valued, then by storing an additional parameter,
a brightness shift B, the 0th pixel of each patch can be converted to 0. 
Method Summary 
static int 
findBigest(byte[] pixels)
finds the index of the bigest item in a vector 
static int 
findSmallest(byte[] pixels)
finds the index of the smallest item in a vector 
float[] 
getBestMatch(byte[] target)
TeX this returns a vector of integers containing the bext match as follows
\begin{tabular}{cccccc}\hline
plane&x&y&rotation&shift&contrast\\
\hline
\end{tabular}
where
plane,x,y indicate the source from which the matching patch can be found;
rotation indicates how many 90 degree clockwise rotations are needed to
bring the source patch into the same orientation as the target;
shift and contrast are used to perform an affine transform in the brightness
space of the source patch to make it as close as possible to the target patch. 
float[] 
getTransform(byte[] target,
int rotation,
byte[] row)
TeX
given a rotated target vector in least first form, the rotation applied to get it to that
form, and a row from the table this derives the optimal transform containing:
\begin{tabular}{cccccc}\hline
plane&x&y&rotation&a&b\\
\hline
\end{tabular}
Let the source vector after rotation be $\{p,q,r,s\}$ and the target vector be
$\{i,j,k,l\}$
\begin{description}
\item[plane] derived from the 5th column of the table
\item[x] derived from the 6th column of the table
\item[y] derived from the 7th column of the table
\item[rotation] Let the rotation required to bring the source
into normal form be $r_s$ and let the
rotation required to bring the target into such alignment
be $r_t$ then the rotation required to bring
the source into alignment with the target is
$r_sr_t$. 
void 
indexPatch(byte[] pixels,
int plane,
int x,
int y)
TeX This is used to enter a group of 4 pixels into the index 
static byte[] 
rotate(byte[] pixels,
int by)
Rotate a vector circularly, models the effect of 90 degree clockwise
rotations on blocks of 4 pixels 
Methods inherited from class java.lang.Object 
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait 
table
public byte[][][][] table
 TeX
\subsection*{Internal representation}
Observe that if the pixels are rotated into an orientation such that the
0th pixel is the lowest valued, then by storing an additional parameter,
a brightness shift B, the 0th pixel of each patch can be converted to 0.
Under this transformation, the stored pixel in the index is converted
to $(pixel_i +B)$. The shift is chosen such that $B=(1 \times pixel_0)$.
An appropriate contrast multiplier M can then convert the brightest pixel,
$pixel_{\em b}$, to the
value 255.
The composition of the two transforms now makes the ith pixel to
$(pixel_i+B)\times M$. The contrast multiplier is chosen such that
$$(pixel_{\em b}+B)\times M=255$$ and thus
$$M=255 \div (pixel_{\em b}+B)$$
Under this transform we have now constrained two of the 4 pixels
to take on the values 0 and 255. Our patch then has only 3 degrees
of freedom, the two intermediate valued pixels, and the position within
the sequence of the brightest pixel, i.e., the value of {\em b}
This encoding allows us to use a 3 dimensional index pointing at the
records in the relation.
The index is then organised so that
the dimensions store the following information
\begin{tabular}{\ll\}\hline
Dimension&Derived from \\ \hline
0& ${\em b}1$\\
1&lowest numbered pixel in range 1..3 other than {\em b}\\
2&highest numbered pixel in the range 1..3 othern than {\em b}\\
3&The table as described in the introduction\\
\hline
\end{tabular}
This enables a fast index to be constructed to find the nearest matching
patch for any given patch
FractalIndex
public FractalIndex()
findSmallest
public static int findSmallest(byte[] pixels)
 finds the index of the smallest item in a vector
findBigest
public static int findBigest(byte[] pixels)
 finds the index of the bigest item in a vector
rotate
public static byte[] rotate(byte[] pixels,
int by)
 Rotate a vector circularly, models the effect of 90 degree clockwise
rotations on blocks of 4 pixels
indexPatch
public void indexPatch(byte[] pixels,
int plane,
int x,
int y)
 TeX This is used to enter a group of 4 pixels into the index
getBestMatch
public float[] getBestMatch(byte[] target)
 TeX this returns a vector of integers containing the bext match as follows
\begin{tabular}{cccccc}\hline
plane&x&y&rotation&shift&contrast\\
\hline
\end{tabular}
where
plane,x,y indicate the source from which the matching patch can be found;
rotation indicates how many 90 degree clockwise rotations are needed to
bring the source patch into the same orientation as the target;
shift and contrast are used to perform an affine transform in the brightness
space of the source patch to make it as close as possible to the target patch.
if $ x$ is a source pixel the transform required is:
$(x+shift)\times contrast$
Note that shift is in terms of fpixels as should x be
getTransform
public float[] getTransform(byte[] target,
int rotation,
byte[] row)
 TeX
given a rotated target vector in least first form, the rotation applied to get it to that
form, and a row from the table this derives the optimal transform containing:
\begin{tabular}{cccccc}\hline
plane&x&y&rotation&a&b\\
\hline
\end{tabular}
Let the source vector after rotation be $\{p,q,r,s\}$ and the target vector be
$\{i,j,k,l\}$
\begin{description}
\item[plane] derived from the 5th column of the table
\item[x] derived from the 6th column of the table
\item[y] derived from the 7th column of the table
\item[rotation] Let the rotation required to bring the source
into normal form be $r_s$ and let the
rotation required to bring the target into such alignment
be $r_t$ then the rotation required to bring
the source into alignment with the target is
$r_sr_t$.
\item[a,b] derived as
\end{description}