Fractal Detection: Short Course
Click here for a larger image.
Environment: Java 2 + Java 3D
Editor's note: This article is about fractals. As such, it should be of interest to anyone regardless of programming langauges. The examples use Java instead of C++; however, I believe you'll find the article of interest. |
A. Introduction
Computers, as we know it, are bit-crunching machines, and everything that they do is the result of bit operations. The simplicity and speed of any program is determined by the number of bit operations required to accomplish a given task and the number of bits that define the program. In the quest for making computers intelligent, programs and programmers succumb to the overwhelming complexity that is required to make intelligence possible. The question of complexity is twofold: what kind of complexity, and how complex is it? Observations show that modern programs are based on computer language environments that have finite structure, and should not be overly complex because a programmer should be able to learn them in a reasonable time. Even then, a complex environment is based on a simple core of the language, or kernel.
Modern programming creates structural complexity: a structure that builds on basic blocks and has to grow in size to become more complex. This kind of complexity becomes inevitably slower and consumes more resources as it grows in size. On the other hand, another kind of complexity is possible, as fractals demonstrate: complex complexity. This kind of structure is made of complex blocks that are connected by complex linking, which is defined by the blocks themselves. This kind of structure is able to become more complex while growing at a slower rate. This article explains how to build these complex blocks.
B. Fractals
Fractals, in non-mathematical terms, are irregular collections of irregular fragments that are also fractals. This definition is iterative and recursive. In programming terms, a fractal is an expression that can be interpreted in other expressions, where each expression has a unique meaning, and where all derived expressions have more meaning than the original and are also fractals. Even shorter, if the meaning is defined as a fractal property, and irregular is defined as unique between derived and the original expressions, an expression that can be expressed by irregular expressions that together mean more than the original. The meaning is subjective for all observers, but the uniqueness and size of the meanings don't change. For instance, consider the expression "Room":
Room | +-Bounds-(walls,ceiling,floor) +-Exits-(doors,windows) +-Furniture-(cabinets,chairs,tables) +-Lights-(fluorescent,incandescent) +-***-(**,**,**)
"Room" here is divided into bounds, exits, furniture, and lights, where each can be divided even further, and each division will have a unique meaning and all divisions together will be more meaningful than "Room" itself. This way, the expression "Room" can be seen as a fractal.
The universe can be seen as a very large fractal that exposes only a small portion to an observer. And yet, however small a portion, it can be divided indefinitely, in theory. In practice, the environment is observed and interpreted by finite expressions that allow an observer to appreciate the infinite possibilities of division.
C. Computers
There is another definition of fractals: a shape that grows in size slower than its perimeter, or to include any number of dimensions, a shape that grows in volume slower than its surface. This is a sort of an inside-out definition of fractals. Instead of viewing a fractal as a whole and dividing it, the fractal is built by introducing "ridges" into a basic shape, or irregularities, that are repeated over and over, in an irregular fashion.
The only reason a growing shape becomes fractal is because irregularities are applied onto themselves, which makes every step in the shape's growth an irregularity more complex than the previous step. The remarkable part is that the original irregularity can be observed in any part of the resulting shape, and recorded. By recording that irregularity, an observer is able to project future and previous steps of the shape growth (macroscopic as the universe, and microscopic as molecules) that are unobservable at the moment. And the accuracy of projection depends on the accuracy of recording.
Memory bits in common computers have only two states: 0 and 1. By increasing the number of bits by n, a computer is able to represent 2n times more states. Inevitably, a computer will suffer from lack of accuracy, or lack of resources while observing the environment. And yet, it doesn't need to be very accurate, because humans are able to derive sufficient meaning from simple expressions. This way, a compromise can be reached where computers can understand humans, and humans—computers.
D. Observation
Computers, being bit machines, observe their environment as sequences of bits. They are able to observe natural environments, like audio and video, as sequences of frames, where a frame is a sequence of bits and has a regular structure. In order to discover irregularities, a computer needs to divide the observed environment into irregular fragments. This can be done in a few different ways. For instance, if a still image is observed, it can be shifted along any vector in 3D space and compared to the original. This way similar fragments can be removed and the rest can be examined. A dynamic input can be examined by comparing a given frame with a number of following frames. That way, irregularities can be discovered in frame-space and frame-time, thus recording not only properties but also behavior of the observed objects.
E. Division
Division is based on comparing the states of the observed environment in time or from different views. This rule holds for any intelligence, whether human or not. Even when looking at an inert object with one eye, humans change eye focus, and their brains perform morph operation, unconsciously.
However the states of the environment are delivered to the computer, they end up in bit form. To determine the difference between the states, the computer has to compare them bit-by-bit. The most effective and suitable operation for that task is XOR (1^0=0^1=1 1^1=0^0=0). XOR in this case displays the areas that changed between the states. To distinguish these irregular areas, a computer can apply the result of XOR to the original state as a mask, where 1s keep the original bit, and 0s change the bit to 0, by using AND (1&0=0&1=0&0=0 1^1=1). However, these areas are nothing but overlap errors, or division lines. To discover divided areas, the computer has to negate the result of XOR and apply it to the original, by using NAND, (NOT mask AND state, ~m&s).
F. Fragments
The divided areas that result from comparing consecutive states display an irregularity that repeats the shape of the observed objects and their behavior, movement, or morph. A computer is able to discover more irregularities in a given state if it performs a multi-frame comparison. The frames are compared between themselves, and the resulting XOR masks are also compared. The reason for comparing XOR masks is that observed irregularities change in an irregular fashion, thus creating a fractal. As a result, XOR masks undergo XOR and NAND operations themselves, and only then are imposed on the states.
The result of the multi-frame comparison is a set of decreasingly fragmented consecutive frames having the most fragmented frame at the beginning and least fragmented at the end.
Let "b" be the number of frames. Let "n" be the fragmentation level. Then, the following algorithm calculates fragments of every frame:
FRAG(n,b)=INAND(n-1,b) NAND FRAME(b) FRAG(0,b)=FRAME(b) INAND(n,b)=IXOR(n,b) NAND IXOR(n-1,b) NAND ... NAND IXOR(0,b) INAND(0,b)=IXOR(0,b) IXOR(n,b)=IXOR(n-1,b) XOR IXOR(n-1,b+1) IXOR(0,b)=FRAME(b) XOR FRAME(b+1)
The least fragmented frame is the frame itself. INAND takes the bottom result of the comparison and performs NAND with the previous result, all the way to the top. IXOR calculates XOR levels for a given frame.
G. Recording
The result of frame fragmentation is a sequence of irregularities. To record an irregularity one must retain its initial state and its changing states. One way to do that is to have an array of 2+ dimensions, where each dimension corresponds to the state values. For instance, if frames are represented in bytes, the array will have 256 bytes in every dimension. A 2D array will be able to record two consecutive states, 3D—three states, and so on. By recording the fragmentation level at which state s1 changed into s2, a block can be built that records all encountered irregularities: block[s1][s2]|=1<<n. Depending on how many bits are in a frame unit, 8 for bytes, 16 for shorts, that number of frames is fragmented and recorded.
For instance, if a frame is made of F bytes, it has L=8 fragmentation levels. A 2D block is built this way:
FOR D=1 D<L D++ FOR P=0 P<F P++ X=FRAG(D ,0)[P] Y=FRAG(D-1,1)[P] BLOCK[X][Y]|=1<<(D-1) IF(D==1) BLOCK[Y][X]|=1<<7 ENDIF END END
In this case, the target level is determined by the resulting state; thus, to get to level 0, an iteration needs to start with level 1 of the source frame. To preserve the integrity of states, the 8th bit is made a reverse pointer. For a 3D block, the iteration is similar:
FOR D=2 D<L D++ FOR P=0 P<F P++ X=FRAG(D ,0)[P] Y=FRAG(D-1,1)[P] Z=FRAG(D-2,2)[P] BLOCK[X][Y][Z]|=1<<(D-2) IF(D<4) BLOCK[Z][Y][X]|=1<<(L-4+D) ENDIF END END
In this case, the iteration needs to start with level 2 to bypass the previous level and reach the target n-2. Now there are two reverse bits.
As a result, a complex block is built that is able to interpret input in a regular sequences of bits. This block is a fractal index; it will produce regular sequences for similar observed objects, or events, independently of their context, thus resulting in accurate recognition.
H. Intelligence
The intelligence of a system is determined by its ability to assimilate diverse input and produce meaningful output. The more flexible and productive a system is, the more intelligent it is.
Complex block programming, or fractal programming, is based on combining complex blocks that are produced from diverse input and causing regular sequences from one block define the actions of another.
I. Questions
Fractal programming is a newborn concept; it opened a number of questions regarding its validity, its current methods, and its future development.
- What is the difference between decreasing and increasing fragmentation?
- What other methods of indexing are possible?
- How classifiable are regular sequences produced by complex blocks?
- What is the optimal method of producing regular sequences?
J. Implementation
Currently, http://sourceforge.net/projects/fractalkiss/ is hosting a set of utilities that build complex blocks and display them visually. Java 2 is used as a prototyping language, thanks to it being cross-platform and having its powerful media processing features. At this point, development is moving into the application stage: a speech recognition application that will be able to run in embedded devices.
Copyright © 2002, Dmitri Pavlenkov.
Downloads
Download demo and source - 138 Kb