[go: up one dir, main page]

WO1997012330A1 - Procede et appareil pour le traitement de l'information au moyen d'une transformee basee sur des automates cellulaires - Google Patents

Procede et appareil pour le traitement de l'information au moyen d'une transformee basee sur des automates cellulaires Download PDF

Info

Publication number
WO1997012330A1
WO1997012330A1 PCT/US1996/015610 US9615610W WO9712330A1 WO 1997012330 A1 WO1997012330 A1 WO 1997012330A1 US 9615610 W US9615610 W US 9615610W WO 9712330 A1 WO9712330 A1 WO 9712330A1
Authority
WO
WIPO (PCT)
Prior art keywords
input data
data
basis
cell
ofthe
Prior art date
Application number
PCT/US1996/015610
Other languages
English (en)
Inventor
Olurinde E. Lafe
Original Assignee
Innovative Computing Group, Inc.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US08/537,080 external-priority patent/US5677956A/en
Application filed by Innovative Computing Group, Inc. filed Critical Innovative Computing Group, Inc.
Priority to AU72013/96A priority Critical patent/AU7201396A/en
Publication of WO1997012330A1 publication Critical patent/WO1997012330A1/fr

Links

Classifications

    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00Image coding
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00Machine learning
    • GPHYSICS
    • G09EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09BEDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS
    • G09B23/00Models for scientific, medical, or mathematical purposes, e.g. full-sized devices for demonstration purposes
    • G09B23/06Models for scientific, medical, or mathematical purposes, e.g. full-sized devices for demonstration purposes for physics
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/30Compression, e.g. Merkle-Damgard construction
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/80Wireless

Definitions

  • the present invention relates to information processing, and, in particular, to applying a cellular automata transform to information processing While the invention is subject to a wide range of applications, it is especially suited to data encoding/decoding systems, data compression/decompression systems, image processing systems, and high speed telecommunication systems, and will be particularly described in that connection Background Art
  • lossy compression In one type of data compression, knoen as "lossy" compression, the reconstructed data is not completely identical to the original
  • applications e.g.. images or video
  • video applications constitute major challenges for current compression technology.
  • Existing interactive video compression hardware is expensive.
  • existing technology degrades the image quality and cannot achieve massive compression in real-time
  • the disclosed invention is capable of achieving rates of real-time information processing and modeling.
  • DCT Discrete Cosine Transform
  • DCT is typically a frame-based compression technique. Data representing a given image is broken into blocks of 64 pixels (8 * 8). A number of arithmetic operations are then performed to implement the transformation process. On a typical 8 x 8 block, DCT originally required 256 operations A refinement of DCT, known as the Generalized Chen Transform, has reduced the 256 operations to 64
  • the Fractal Transform was developed by Michael Barnsley and Alan Sloan (U.S. Patent No. 4,941, 193 and 5,065,447) and exploits the self-similarities inherent in most images Parts ofthe image, when translated, rotated, and scaled are used as the basic building blocks of other portions ofthe image
  • the encoding and decoding processes are both iterative
  • the encoding process is computationally intensive
  • the decoding is reportedly quicker
  • the Wavelet Transform involves the decomposition ofthe data into a set of basis functions known as wavelets, as reported by S G Mallat in "A Theory of Multiresolution Signal Decomposition the Wavelet Representation," Comm. Pure and Appl. Math . 41 , 7, 674-693, 1988
  • the major drawback ofthe Wavelet Transform is the computational difficulty in generating the basis
  • lossless compression techniques include the Huffman Method, the Arithmetic Method, and the Dictionary Method
  • Huffman Method is a statistical encoder in which variable-length codes of integral numbers of bits are created Shorter codes are assigned to symbols with high probabilities More sophisticated versions ofthe original Huffman Method make use of higher-order statistics
  • a given message is represented by an interval of real numbers between 0 and 1 The longer the message gets, the longer the interval needed to represent it
  • Encoders that employ the Dictionary Method use single tokens to represent symbols with variable lengths An index to a dictionary is formed using the tokens
  • the LZW compression method is an example ofthe Dictionary Method, which extends the alphabet with additional strings used to represent strings of regular characters
  • LZW is the compression used in the GIF file format (a standard developed by CompuServe for transmitting and storing image files), the UNIX COMPRESS program, and the compression/decompression software known as PKZIP
  • PKZIP compression/decompression software
  • the major disadvantages ofthe lossy encoders generally include one or a combination ofthe following 1 ) high computational intensity, 2) a limited/small family of transform bases, 3) large encoding errors at high compression ratios
  • the processing time in particular, constitutes a significant barrier towards achieving routine or real-time compression in various applications
  • Data is encrypted, that is, scrambled, for security during transmission or storage.
  • encryption techniques using dynamic systems have been developed in recent years
  • J Kari has also described an encryption technique that uses reversible dynamical systems J-P, Delahaye, "Les Automates,” Pour La Science, pp 126-134, 1991
  • Cellular automata can be defined as dynamic systems in which space and time are discrete
  • the cells of a cellular automata space are arranged in a lattice structure and have a finite number of states These states are updated synchronously according to specified local rules of interaction
  • a two-state, one-dimensional cellular automata space consists of a line of cells (also called “sites"), with each cell capable of taking one of two values such as "0" or " 1 "
  • sites also called "sites”
  • each cell capable of taking one of two values such as "0" or " 1 "
  • the value of each cell is updated synchronously in discrete time steps
  • the phenomena being modeled can originate from complex systems derived from physics (e g., fluid dynamics, heat conduction, deformation of solids), chemistry (e g , diffusion-controlled reactions), biology (e g , cell reproduction), or economics (e g . financial market analysis)
  • a computer receives input data, generates a CA basis from a combination of key values, and transforms the input data into encoded data using the CA basis.
  • CA cellular automata
  • Decoding of encoded data is performed by a computer that receives encoded input data, generates a C A basis from a combination of key values, and transforms the encoded data using the basis into decoded data using the CA basis
  • a computer implemented transform is employed to model a physical system
  • the method of modeling of a physical system includes the steps of receiving input data describing characteristics ofthe physical system, generating a CA basis from a combination of predetermined key values, and transforming the input data using the CA basis into a model ofthe physical system described by the input data
  • the invention includes an apparatus for information processing and modeling
  • This apparatus includes a receiver for receiving input data and a key value, an input device, a programmed control interface, read only memory, a processing unit, a cell state random access memory, a cell coefficient random access memory, and a transmitter
  • the transmitter transmits any key value used to generate a CA basis used to transform input data into output data
  • This transmitter also transmits output data
  • Fig 1 is an illustration of three-cell neighborhoods in a CA lattice
  • Fig 2 is an illustration of the application of a local rule of interaction to a three-cell CA neighborhood.
  • Fig 3 shows the iteration of CA cell states at four time intervals
  • Fig 4 is a block diagram of an apparatus for computing the CA transform according to the present invention.
  • Fig 5 is a flow diagram for CA encoding of data according to a preferred implementation of the present invention.
  • Fig 6 is an illustration of a CA key and CA key values according to the present invention.
  • Fig 7 is an illustration of a data string used to explain the S-bases according to the present invention.
  • Fig 8 is a flow chart showing the CA transform using an S-basis according to the present invention.
  • Fig 9 illustrates examples of 7 basis types according to the present invention
  • Fig 10 is a block diagram illustrating C A transform compression and decompression of an image according to a preferred implementation ofthe present invention
  • Fig 1 1 is a table showing the CA coefficients associated with the 8-bit grey scale subimages (each 8 * 8) of different portions of a digitized image of a human face,
  • Fig 12 is a block diagram showing data encryption and decryption using the CA transform according to a preferred implementation ofthe present invention
  • Fig. 13 is a block diagram illustrating modeling of a physical system using the CA transform according to a preferred implementation ofthe present invention Best Mode for Carrying Out the Invention
  • Cellular automata are dynamic systems in which space and time are discrete
  • the ceils which are arranged in the form of a regular lattice structure, have a finite number of states These states are updated synchronously according to a specified local rule of interaction
  • a 2-state 1 -dimensional cellular automaton will consist of a set of cells (sites), each of which can take value 0 or 1
  • sites cells
  • rules the values for all cells are updated simultaneously in discrete time steps
  • An example of a rule is the expression that the value of each cell at a specific time interval is equal to the sum of the values of its immediately adjacent neighbor cells at the previous time interval
  • each cell can take any of the integer values between 0 and k- ⁇
  • the rule governing the evolution ofthe cellular automaton will encompass r sites up to a finite distance away
  • such a cellular automaton is a Estate, r-site neighborhood CA
  • a CA-based technology offers a favorable computational environment for compressing and decompressing data in real time
  • the greatest advantage is that the underlying computational procedure uses Boolean computation, the natural language of computers, and thus does not devour time and computational resources by performing complicated floating point computations
  • the computational simplicity translates into extremely fast data processing speed
  • Fig 1 illustrates an eleven cell lattice 100 with cells 1 lOa-k some of which are grouped in three exemplary cell "neighborhoods" 120a-c as shown by dashed lines
  • Each neighborhood 120a-c comprises a one-dimensional CA space
  • the state of each cell 1 1 Oa-k is given by the Boolean variable a When the state is on, a ⁇ 1 , otherwise it is off and a ⁇ 0
  • the quantity a ; represents the state (Boolean) ofthe /-th cell, at discrete time /, and whose two neighbors are in the following states a, réelle and a,.co
  • the present invention implements a rule that will be used to synchronously calculate the state a amid + , from the state ofthe cells in the neighborhood at the t-t time level.
  • the cellular automaton evolution is expressible in equation (1): a,
  • is a Boolean function defining the rule
  • Fig. 2 illustrates application of a rule (to be described below) over one time interval for a one dimensional CA
  • the variables at each cell may take values 0 or 1
  • the eight possible states of three adjacent cells are given in the left hand column and constitute the configurations C 0 -C 7 set forth above
  • the right hand column gives the result of the application ofthe rule for the time evolution of the CA by giving a j( the value to be taken by the central cell 1 lOf of the three cells at the next time interval.
  • boundary configurations the assumptions dictating which cells are neighbors of cells at the edge of a CA lattice, are derived from the evolving lattice (cell states change over successive time intervals) by imposing a periodic (cyclic) condition
  • a cyclic boundary condition means that cells on the left 1 lOd and right edges 120c of a CA lattice are considered neighbors for purposes ofthe application ofthe rule of interaction
  • A-state/r-site N-cells CA over T time steps is ofthe order
  • Fig 3 illustrates the evolution of cell states over four time intervals
  • a different rule, Wolfram rule 203 is applied to a two-state, three-site neighborhood in a four-cell lattice using cyclic boundary conditions.
  • the first row represents the cell states in their initial configuration
  • the second, third, and fourth rows represent cell state values after the first, second, and third application ofthe CA Wolfram rule 203, respectively.
  • the preferred implementation ofthe present invention uses a CA transform to encode and decode data This CA transform is specified in equation (3)
  • the function f is defined in a physical space of lattice grid i using basis A and associated transform coefficients c
  • the variable k is an index that refers to the CA space of a lattice grid
  • the elements A ⁇ of basis A are generated from the states ofthe CA cells a ⁇
  • Each element A ⁇ is generated according to specified characteristics described below
  • Equation (3) represents a mapping ofthe function f (in the physical domain) into c (in the CA space) using the basis A to define the mapping A strength of this invention is the huge number and varied nature ofthe basis that can be generated
  • the basis A comprises the building blocks used to construct the function f
  • the building blocks possess a plurality of shapes, which will be explained further below
  • the coefficients c measure the size of each basis required to reconstruct f
  • f represents, for example, data
  • c represents an encoded version ofthe same data (e.g , compressed data)
  • basis A represents the function used to encode the data
  • Fig 4 is a block diagram of a preferred CA transform apparatus 400 in which the CA transform represented by equation (3) may be implemented
  • Other apparatus types for example, general purpose computers, may be used to implement the CA transform represented by equation (3)
  • Apparatus 400 is comprised of a receiver 402, an input device 405, a programmed control interface 404, control read only memory (“ROM”) 408, control random access memory (“RAM”) 406, process parameter memory 410, processing unit PU 416, cell state RAM 414, coefficient RAM 420, disk storage 422, and transmitter 424.
  • Receiver 402 receives data from a transmitting data source for realtime (or batch) processing of information such as satellite imagery. Alternatively, data awaiting processing by the present invention (e.g., archived images) are stored in disk storage 422.
  • the present invention preferably performs information processing according to programmed control instructions stored in control ROM 408 and/or control RAM 406
  • Information processing steps that are not fully specified by instructions loaded into control ROM 408 may be dynamically specified by a user using an input device 405 such as a keyboard
  • a programmed control interface 404 provides a means to load additional instructions into control RAM 406
  • Process parameters received from input device 405 and programmed control interface 404 that are needed for the execution ofthe programmed control instructions are stored in process parameter memory 410
  • key values needed to compute a CA transform and any default process parameters can be preloaded into process parameter memory 410
  • Transmitter 424 provides a means to transmit the results of computations performed by the CA transform apparatus and process parameters used during computation.
  • the preferred apparatus 400 consists of at least one module 412 comprising a processing unit (PU) 418 and a cell state RAM 416.
  • Module 412 is a physical manifestation of the CA cell In an alternate embodiment more than one cell state RAM may share a PU
  • the transform apparatus 400 shown in Fig 4 can be readily implemented in parallel processing computer architectures ln a parallel processing implementation, processing units and cell state RAM pairs, or clusters of processing units and cell state RAMs, are distributed to individual processors in a distributed memory multiprocessor parallel architecture
  • Fig 5 is a flow diagram showing the steps common to performing information processing using the present invention
  • a process type is specified (step 502)
  • the process type indicates the specific type of applications to which the present invention will be directed It can be preprogrammed in control ROM 408, determined dynamically from user input via the user interface 404, or read from a software control program loaded into control RAM 406
  • the present invention transforms physical signals received by receiver 402 or stored in memory (disk storage 422)
  • Examples of information processing application ofthe present invention include data compression/decompression, encryption/decryption, and image processing
  • the second category of process types, information modeling encompasses all aspects of phenomena modeling/simulation These aspects include those derived from physics (e.g , fluid dynamics, deformation of solids, heat conduction, optics, acoustics, transport processes in porous media, etc ), chemistry (e g , electrochemistry, diffusion- controller reactions, chemical turbulence, kinetics, etc ), biology (e g , cell reproduction, neurology, artificial life, etc ), and economics (e g , financial market analysis, etc )
  • physics e.g , fluid dynamics, deformation of solids, heat conduction, optics, acoustics, transport processes in porous media, etc
  • chemistry e.g , electrochemistry, diffusion- controller reactions, chemical turbulence, kinetics, etc
  • biology e g , cell reproduction, neurology, artificial life, etc
  • economics e g , financial market analysis, etc
  • step 504 the relevant process parameters are entered (step 504)
  • the process parameters may vary for each process type
  • the process parameters like the selection ofthe process type, can be preloaded or established dynamically
  • gateway key is specified either by a user or by choosing from among preloaded gateway key values stored in control memory (step 506) These gateway key values are described in detail below
  • CA transform bases are generated (step 508)
  • the computations required to generate the CA bases are performed by the PU 416.
  • CA transform coefficients, in the form of encoded data, are computed by the PU 416 (step 510) as well
  • CA transform coefficients may optionally be stored in memory 420 or transmitted via a transmitter 424 (step 512)
  • the gateway key that was specified (step 506) and used to generate the CA transform basis (step 508) are also either stored in memory 410 or transmitted via transmitter 424 CA Transform (Gateway Kev
  • CA transform gateway
  • Fig 6 The preferred implementation uses a CA transform (gateway) key 600 consisting of a set of key values 602-620 illustrated in Fig 6
  • This key 600 contains the building blocks, or parameters, necessary to fully specify a CA transform for a particular information processing or modeling application
  • the key values 602-620 include
  • Key value 1 specifies a rule of interaction of the cells within a defined neighborhood, for example rule 90 (discussed above)
  • Key value 2 (604) specifies the number of states allowed for each cell For example, a binary cell has two states
  • Key value 3 indicates the number of cells within each neighborhood Fig 1 illustrates several three-cell neighborhoods
  • Key value 4 defines the total number of cells in the entire lattice Fig. 3 illustrates a four cell lattice
  • Key value 5 defines the initial configuration of the cells
  • Key value 6 defines the boundary configuration ofthe cells For many applications, a cyclic boundary configuration yields the best results
  • Key value 7 specifies the geometric structure ofthe CA lattice For example, CA lattice 302 has cells arrayed in a line segment
  • Key value 8 specifies the dimensionality ofthe CA lattice CA lattice 302, for example, is a one-dimensional lattice
  • Key value 9 specifies the type ofthe CA transform
  • Representative types of CA transforms include standard orthogonal, progressive orthogonal, non- orthogonal, and self-generating transforms Each of these transform types is discussed in detail below
  • Key value 10 specifies the CA basis type, also discussed in detail below
  • the selection ofthe key values 602-620 governs the properties ofthe CA transform ln most applications ofthe present invention, some ofthe key values 602- 620 will be fixed (e.g , key values 3, 4, and 7) for certain classes of information processing and modeling problems
  • One of ordinary skill in the art will be able to vary the key values to achieve optimum performance for a particular information processing and modeling application within an application class.
  • the entire input function is used in determining all ofthe transform coefficients
  • the transformation error is zero if none ofthe coefficients is quantized, that is, none have been approximated, and every coefficient is used in the reconstruction of the input data Orthogonal transformation permits the determination of transform coefficients without the need for elaborate and complex matrix inversion procedures
  • Non-orthogonal transforms include the self-generating CA transform.
  • the inherent similarity that exists in different parts of a given data sequence, self-similarity can be exploited in a compact encoding ofthe data bv using CA ' -bases (discussed below) ln certain instances it is possible, sta ⁇ ing from an arbitrary or random function, to achieve an accurate reconstruction ofthe encoded data, via an iterative transformation called self-generation.
  • Self-generation may not be guaranteed regardless ofthe magnitude ofthe error allowed in the self-similar transformation of the data
  • the present invention embodies two types of self-generation ( 1 ) strong self-generation and (2) weak self-generation Strong self-generation is characterized by the ability to recover encoded data using a CA transform by application of an _S ' -bas ⁇ s starting from an initial arbitrary sequence.
  • Self-generation is weak when the recovery ofthe encoded data can only be achieved from a specified initial data set ln CA transforms, the chief attraction of weak self-generation is the ease with which convergence during decoding can be guaranteed by the CA selection process in the encoding phase ofthe data processing
  • CA gateway values which ensure convergence to the given data, starting from a specific initial set are used The initial set may be formed by simply assigning the same constant value for all data points Types of C A Bases
  • a CA basis is characterized by one (or a combination) ofthe following features.
  • the first class of bases is referred to as the ⁇ -class Elements in this class are comprised of the integers -1, 1 for non-windowed and -1,0, 1 for windowed
  • p-bases whose elements are generated from the CA cell density of the evolving CA space
  • the CA cell density is the number of cells attaining a specified state or the number of times a given state has been attained by a specified cell Therefore, p-bases always have integer values and are suitable for lossless data encoding
  • a third class of bases, ⁇ -bases are generated from the CA cell density ofthe evolving CA space for multiple cells divided by a number corresponding to at least a subset ofthe total number of cells
  • the ⁇ -bases have floating point elements
  • S-bases. a fourth class can be windowed or non-windowed In a windowed S- basis a subset of the basis elements is set equal to zero
  • the transform coefficients consist of scaling parameters that connect segments of data with other segments ofthe same data Therefore, CA transformation using an S-basis can result in significant data compression when the redundancy resulting from data self-similarity is exploited
  • Fig 7 is a flow diagram ofthe steps for computing an S-basis CA transform using the present invention.
  • a set of CA key values are randomly selected (step 640)
  • the input data is divided into segments (642) In general, the segments may overlap The overlapping of segments will yield a greater fidelity in encoding at the expense of an increased number of parameters and increased encoding time
  • the next step is to calculate a set of weights such that using these weights, the value of a given reconstructed data point is a weighted sum of the entire data sequence (step 644)
  • CA transform the data using an S-basis and the weights computed at step 646
  • compare the reconstructed data sequence is compared with the original data sequence (step 648)
  • the reason for reconstructing the data during the encoding process is to ensure the repeated application ofthe S-basis CA transform will actually converge to the original data If the reconstruction error (the difference between the data sequence being encoded and the reconstructed data sequence that resulted from transformation) using the selected key is acceptable
  • a type 1 basis falls under the ⁇ class of CA bases
  • the CA state at cell i, at time k. is represented by a, k
  • a type 2 basis is an example of a p class of CA bases
  • the correspondence between the value of a basis element and a cell state follows Table 1 below For example, following equation 5 when cell a ⁇ is 1 and cell a ⁇ is 1 , the basis element A ⁇ is 1
  • a type 3 basis is an example of a ⁇ class of CA bases
  • the value ofthe basis element A ⁇ corresponds to the average number of cells that have a value of 1 in a specified range of cells and may be represented by equation 6
  • a type 4 basis are examples ofthe p class of CA bases
  • a type 4 basis element A ⁇ is computed using equation 7 from the density a CA cell i, at time k, multiplied by the density of a CA cell k at time i
  • a type 5 basis element like a type 4 basis, is the product of two cell densities, however, in a type 5 basis each cell density is modulated prior to multiplication Modulation, in this sense, means periodically resetting the cell density value to zero once a threshold has been exceeded Equation 8 explains the computation of type 5 basis elements
  • a type 6 basis is another example of the p class of CA bases.
  • the value ofthe basis element corresponds to the product of the average CA cell densities, as explained in equation 9.
  • a * is the basis obtained using the non-windowed types such as type 3 explained above.
  • Type 7 bases are orthogonal for a large class of CA rules and initial boundary configurations. Those skilled in art will recognize that there are many other types of bases including, for example, two-dimensional or multi-dimensional bases. Special Characteristics of CA Bases
  • Non-windowed bases especially those of two-dimensional Type 8 in the ⁇ class, provide an automatic feature extraction capability with compression.
  • the CA coefficients for these bases exhibit a clear and distinct structure. This feature can be exploited for efficient storage and in image segmentation.
  • the table in Fig. 1 1 shows the CA coefficients associated with the 8-bit grey scale subimages (each 8 ⁇ 8) of different portions of a digitized image of a human face. The selected subimages are chosen at random.
  • the large coefficients in Group C, at odd-numbered rows and column locations mainly represent the texture ofthe image.
  • Windowed bases of any class and type are orthogonal, in the progressive sense, over a plurality of CA rules, initial configuration, and boundary configurations
  • the special configuration wherein all the initial cell states are on (or given the value 1 ), and the boundary condition is cyclic results in progressive orthogonal bases of all types and classes with excellent data compression characteristics.
  • CA transforms In using CA transforms for compression, data redundancy is identified by transforming the data into the CA space
  • the principal strength of compression using CA transforms is the large number of transform bases available
  • the present invention preferably employs CA bases that maximize the number of transform coefficients with zero or near zero magnitudes
  • Certain data compression applications desire a transform that always provides a predictable coefficient pattern Using bit encoders known in the art, the predictability of coefficient patterns allows such encoders to concentrate on a targeted subset of coefficients.
  • CA transforms permit the selection of bases that can be adapted to the peculiarities of the data.
  • a strength of CA compression is the Boolean character and parallel nature of the computational process involved in the calculation ofthe evolving states ofthe CA. This can translate into an enormous computational speed improvement in a well-designed encoder using a CA transform.
  • FIG. 10 An implementation of the present invention for encoding of a digital image using the CA transform to perform image data compression of an exemplary image is illustrated in Fig. 10.
  • An image file 702 with pixel value decimal equivalent 704 is passed through a CA transform ("CAT") encoder 706
  • CAT CA transform
  • Example image file 702 would require one hundred twenty-eight bits to encode the entire image without CA transform compression.
  • the CAT encoder 706 requires key values 708 to transform the input image data.
  • Fig 4 illustrates an apparatus 400 that is suitable for this CAT encoder
  • the key values used for this illustration are given in Table 2.
  • a CA space is defined by key values 708
  • Type of CA Basis Type 7 (Type 6, with a window size of 2)
  • the cell space is one dimensional, a single row of four CA cells, CA lattice 710 Rule 203 for local interaction among cells is applied to neighborhoods of three cells Each cell takes on one of two possible states “on” (cell has a value of 1 ) or "off' (cell has a value of 0) Row 710 shows the CA cells in their initial configuration
  • Row 712 shows the CA cells after one time interval, i e , one iteration of applying rule 203 to the each cell neighborhood
  • Rows 714 and 716 show the CA lattice after two and three iterations respectively
  • the boundary configuration in each iteration is cyclic
  • the CA cell states shown in row 716 are used by CAT encoder 706 to generate a type 7 CA transform basis
  • the type 7 basis is a windowed type 6 basis and is, therefore, a member ofthe p class of CA bases Using this type 6 basis, the image is encoded into CA transform coefficients 720 using a progressive orthogonal CA transform
  • CA coefficients 720 can be quantized by quantizer 722 to produce quantized CA transform coefficients 724
  • the quantizer 722 applies a rounding operation
  • CA transform image compression is further enhanced by ordering the transform coefficients using a CA transform coefficient orderer 726 so non-zero coefficients are grouped together
  • Row 734 ofthe encoded binary CA transform data 732 indicates that the first CA transform coefficient has a decimal value of 2 (10 in binary) and a flag (binary 1 ) indicating that this CA transform coefficient is repeated
  • Row 736 indicates that the CA coefficient value identified in the previous row, is repeated three times (1 1 in binary)
  • Row 738 of the encoded binary file indicates that the next CA transform coefficient has a value of 0 (00 in binary) and is not repeated (flag set to binary 0)
  • the last row 740 ofthe encoded data file shows a CA transform coefficient with a value of 1 (01 binary) that is not repeated (flag is set to binary 0)
  • this entire image is encoded using twelve bits Accordingly, the using the present invention to compress the example image, greater than 10 1 compression is achieved
  • Bit decoder 742 decodes the bit encoded binary CA transform data 732 to produce the quantized CA transform coefficients 744
  • the order ofthe coefficients 748 is restored by the inverse CA ordering unit 746
  • the inverse quantizer 750 restores the CA transform coefficients to their original value
  • CA transform coefficient 754 is not recovered exactly because of round-off error in coefficient quantization during image compression
  • the CAT decoder 756, also implemented using apparatus 400 of Fig 4, uses the key values 708 specified during image compression to inverse CA transform the CA coefficients 752 to produce recovered uncompressed image 758 (pixel value representation) represented alternatively as 760 (gray level representation)
  • the present invention thus discloses efficient means to exploit the CA transform for information processing
  • the present invention is particularly suited for digital data processing related to a wide variety of applications including but not limited to medical imaging, high definition television, video telephony, facsimile devices, digital photography, satellite communications, digital video interaction, computer data storage, wireless/cellular telephony, video transmission via telephone systems, remote sensing, data transmission in computer networks, communications via modems, digitized photocopying, video on demand, printers, image/pattern recognition, transmission of weather data, cable television transmission, teleconferencing, x-rays, magnetic resonance imaging, speech recognition, audio recording, lasers, passive transponders, and millimeter-wave radio transmission Data Encryption
  • CA transform bases which are capable of lossless encoding include both windowed and non-windowed ⁇ - and / O-types
  • the transform coefficients have to be non-quantized integers, otherwise errors due to floating-point calculations may result during the decoding phase.
  • the focus is on data security If a message is encoded using the present invention, a code breaker must contend with searching through different key values such as rules, initial configurations, boundary configurations, window sizes, and types of CA bases The odds against code breakage increase tremendously as the number of states, cellular space, neighborhood, and dimensionality increase.
  • FIG. 12 An implementation of the present invention for CA transform based data encryption is illustrated in Fig. 12. Unencrypted data 802 shown in integer format 804 is fed into CAT encoder 806. A CA transform key 808 (including key value) is selected to generate encrypted data 810 shown in integer form 812 The key values of key 808 used by the CAT encoder 806 to generate encrypted data 810 are provided in Table 3.
  • Type of CA Basis Type 7 (Type 3, with a window size and averaging length of 8 cells)
  • the integer representation ofthe encrypted data 812 illustrates that without knowledge ofthe key values and CAT process used to encrypt the data, the relationship between the unencrypted data 804 and the encrypted data 812 would not be apparent to an unauthorized recipient
  • the present invention thus discloses efficient means to exploit the CA transform for data encryption/decryption System Modeling
  • the CAT encoder ofthe present invention can also be used for modeling of physical systems (Fig 13)
  • parameters representative ofthe physical system 902 are specified
  • the plate surface temperature at the left edge and lower edge are fixed at zero degrees
  • a final parameter ofthe physical characteristics of plate 903 is the relationship between the spatial coordinates, conductivity, and temperature It is known that in physical systems such as plate 903 the divergence ofthe product of the conductivity and the gradient of the plate temperature is equal to zero,
  • C A key generator 906 generates keys for CAT encoder 904
  • the CA key generator 906 continues to generate keys and the CAT encoder 904 executes successive CA transforms until the transform performed by CAT encoder 904 produces a model consistent with physical system parameters 902
  • topological key values (2, 3, 4, 6, 7, and 8) are chosen to map to the physical characteristics ofthe system being modeled and remain fixed during key generation
  • the other key values are selected, consistent with the search for CA transform bases, A, which best represent the physical system.
  • the transform coefficients, c are determined to ensure the satisfaction of external conditions (e.g., the temperature profile along the boundaries) imposed on the system.
  • the transform coefficients, c are themselves the solution (in this example, the temperature field) to the physical system.
  • One of ordinary skill in the art will recognize that there are other techniques available for generating an appropriate CA key.
  • the CA transform coefficients 908 that correspond to the generated CA key represent a model of the temperature distribution 909 in plate 903
  • the CA key for this physical system is given in Table 4
  • Type of CA Basis Type 7 (Type 3, with a window size and averaging length of 8)
  • the present invention thus discloses efficient means to exploit the CA transform for information processing and modeling As it has been described, the present invention is particularly suited for image processing and modeling of physical systems Persons of ordinary skill will recognize that modifications and variations may be made to this invention without departing from the spirit and scope ofthe general inventive concept. This invention in its broader aspects is therefore not limited to the specific details or representative methods shown as described

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Mathematical Physics (AREA)
  • Signal Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Evolutionary Computation (AREA)
  • Artificial Intelligence (AREA)
  • Computer Security & Cryptography (AREA)
  • Medical Informatics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Algebra (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Business, Economics & Management (AREA)
  • Educational Administration (AREA)
  • Educational Technology (AREA)
  • Multimedia (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

L'invention concerne un procédé et un appareil pour le traitement de l'information dont le codage et décodage de données, le cryptage et décryptage de données et la modélisation de phénomènes physiques à l'aide d'une transformée qui dépend de données d'entrée et d'une base. Une fois les données d'entrée reçues, la base est générée à partir de valeurs clés spécifiant les caractéristiques d'un espace d'automates cellulaires d'au moins une cellule et au moins une règle d'interaction pour au moins ladite cellule. Les données d'entrées sont transformées en données codées à l'aide de la base générée.
PCT/US1996/015610 1995-09-29 1996-09-27 Procede et appareil pour le traitement de l'information au moyen d'une transformee basee sur des automates cellulaires WO1997012330A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU72013/96A AU7201396A (en) 1995-09-29 1996-09-27 Method and apparatus for information processing using cellular automata transform

Applications Claiming Priority (6)

Application Number Priority Date Filing Date Title
US53708195A 1995-09-29 1995-09-29
US53708695A 1995-09-29 1995-09-29
US08/537,086 1995-09-29
US08/537,081 1995-09-29
US08/537,080 1995-09-29
US08/537,080 US5677956A (en) 1995-09-29 1995-09-29 Method and apparatus for data encryption/decryption using cellular automata transform

Publications (1)

Publication Number Publication Date
WO1997012330A1 true WO1997012330A1 (fr) 1997-04-03

Family

ID=27415235

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1996/015610 WO1997012330A1 (fr) 1995-09-29 1996-09-27 Procede et appareil pour le traitement de l'information au moyen d'une transformee basee sur des automates cellulaires

Country Status (2)

Country Link
AU (1) AU7201396A (fr)
WO (1) WO1997012330A1 (fr)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001050457A1 (fr) * 1999-12-30 2001-07-12 Quikcat.Com, Inc. Procede et dispositif de compression audio a l'aide d'un systeme dynamique
WO2001050456A1 (fr) * 1999-12-29 2001-07-12 Quikcat.Com, Inc. Codage de donnees audio d'apres une synthese des sons granulaires
DE102004025566A1 (de) * 2004-04-02 2005-10-27 Conti Temic Microelectronic Gmbh Verfahren und Vorrichtung zum Analysieren und Bewerten eines Signals, insbesondere eines Sensorsignals
WO2014203039A1 (fr) 2013-06-19 2014-12-24 Aselsan Elektronik Sanayi Ve Ticaret Anonim Sirketi Système et procédé de mise en œuvre d'un calcul de réservoir à l'aide d'automates cellulaires
CN110113765A (zh) * 2019-05-07 2019-08-09 四川大学 一种基于元胞自动机模型的信息源定位算法
CN119810227A (zh) * 2024-12-10 2025-04-11 中南大学 一种基于元胞自动机的纹样自动生成方法及其系统

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0257581A2 (fr) * 1986-08-29 1988-03-02 International Business Machines Corporation Système de traitement d'images à réseau maillé polymorphe

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0257581A2 (fr) * 1986-08-29 1988-03-02 International Business Machines Corporation Système de traitement d'images à réseau maillé polymorphe

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
HASSELBRING W: "CELIP: A CELLULAR LANGUAGE FOR IMAGE PROCESSING", PARALLEL COMPUTING, vol. 14, no. 1, 1 May 1990 (1990-05-01), pages 99 - 109, XP000171588 *
YING LIU: "FRACTALS, NEURAL NETWORKS, CELLULAR AUTOMATA, FORMAL LANGUAGE AND CODING THEORY", EMERGENT INNOVATIONS ON INFORMATION TRANSFER PROCESSING AND DECISIO MAKING, CHICAGO, OCT. 18 - 21, 1992, vol. 2 OF 2, 18 October 1992 (1992-10-18), INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, pages 1663 - 1669, XP000379009 *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001050456A1 (fr) * 1999-12-29 2001-07-12 Quikcat.Com, Inc. Codage de donnees audio d'apres une synthese des sons granulaires
WO2001050457A1 (fr) * 1999-12-30 2001-07-12 Quikcat.Com, Inc. Procede et dispositif de compression audio a l'aide d'un systeme dynamique
US6567781B1 (en) 1999-12-30 2003-05-20 Quikcat.Com, Inc. Method and apparatus for compressing audio data using a dynamical system having a multi-state dynamical rule set and associated transform basis function
DE102004025566A1 (de) * 2004-04-02 2005-10-27 Conti Temic Microelectronic Gmbh Verfahren und Vorrichtung zum Analysieren und Bewerten eines Signals, insbesondere eines Sensorsignals
WO2014203039A1 (fr) 2013-06-19 2014-12-24 Aselsan Elektronik Sanayi Ve Ticaret Anonim Sirketi Système et procédé de mise en œuvre d'un calcul de réservoir à l'aide d'automates cellulaires
CN110113765A (zh) * 2019-05-07 2019-08-09 四川大学 一种基于元胞自动机模型的信息源定位算法
CN119810227A (zh) * 2024-12-10 2025-04-11 中南大学 一种基于元胞自动机的纹样自动生成方法及其系统

Also Published As

Publication number Publication date
AU7201396A (en) 1997-04-17

Similar Documents

Publication Publication Date Title
US6456744B1 (en) Method and apparatus for video compression using sequential frame cellular automata transforms
Memon et al. An analysis of some common scanning techniques for lossless image coding
US10382789B2 (en) Systems and methods for digital media compression and recompression
US5677956A (en) Method and apparatus for data encryption/decryption using cellular automata transform
CN111699696A (zh) 用于对字节流进行编码和解码的方法和设备
Song et al. Joint image compression–encryption scheme using entropy coding and compressive sensing
Boussif et al. Securing DICOM images by a new encryption algorithm using Arnold transform and Vigenère cipher
JPH0630391A (ja) 大域ブロック変換を用いた圧縮画像データに頑強性を付与するための装置および方法
EP0628232A1 (fr) Codage fractionne de donnees
US6393154B1 (en) Method and apparatus for digital image compression using a dynamical system
Jindal et al. Image and video processing using discrete fractional transforms
Hung et al. Error-resilient pyramid vector quantization for image compression
Ravi et al. Optimized wavelet filters and modified huffman encoding-based compression and chaotic encryption for image data
Wang et al. Autoencoder-based joint image compression and encryption
Arya Robust image compression algorithm using discrete fractional cosine transform
Liu et al. Image processing method based on chaotic encryption and wavelet transform for planar design
Wang et al. A customized deep network based encryption-then-lossy-compression scheme of color images achieving arbitrary compression ratios
Ferdowsi et al. Privacy-preserving image sharing via sparsifying layers on convolutional groups
Long et al. Improved fractal coding and hyperchaotic system for lossless image compression and encryption
US6330283B1 (en) Method and apparatus for video compression using multi-state dynamical predictive systems
EP1796397B1 (fr) Méthode de codage vidéo réversible par étape, méthode de décodage vidéo réversible par étape, dispositif de codage vidéo réversible par étape, dispositif de décodage vidéo réversible par étape, programme pour cela
WO1997012330A1 (fr) Procede et appareil pour le traitement de l'information au moyen d'une transformee basee sur des automates cellulaires
TW200531456A (en) Repetition coded compression for encrypting highly correlated data
Latha et al. HWCD: A hybrid approach for image compression using wavelet, encryption using confusion, and decryption using diffusion scheme
US6400766B1 (en) Method and apparatus for digital video compression using three-dimensional cellular automata transforms

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AL AM AT AU AZ BA BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GE HU IL IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK TJ TM TR TT UA UG US UZ VN AM AZ BY KG KZ MD RU TJ TM

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): KE LS MW SD SZ UG AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA