Computer graphics processing and selective visual display system – Computer graphic processing system
Reexamination Certificate
1999-06-23
2002-05-21
Tung, Kee M. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphic processing system
C382S254000
Reexamination Certificate
active
06392653
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of processing operations carried out on acquisition data. These data relate to physical representations such as two-dimensional or three-dimensional images, for which it is possible to define a neighbourhood relationship between the elements which constitute them.
Such acquisition data are provided in the form of a sequence of elements, comprising at least one bit per element. In the case of a two-dimensional image, each element of the image (or pixel) has its own attributes, for example colours and/or grey scale levels coded on a certain number of bits. It will thus be understood that the pixels on a line of a black and white two-tone two-dimensional image may have a “black” attribute, while the pixels of the background have a “white” attribute. These attributes are then coded on a “0” or “1” bit, for example “0” for “white” and “1” for “black”. As for the position of the pixel, this can be coded according to the column and the row to which it belongs. These two data items are generally recorded in memory in order to extract information about the image therefrom (characteristic point sets), or alternatively to create subsequent modifications to the image, such as erosion, dilation and/or thinning of lines (and/or surfaces in the case of a three-dimensional image).
These various processing operations generally consist in attributing to a current element a “result word” which is a function of a comparison of the respective bits of neighbouring elements in the sequence of this current element. In practice, this comparison is made on the basis of successive tests on the bits of the elements which define a chosen neighbourhood of the current element.
PRIOR ART
The conventional devices which perform such processing operations proceed according to two different general techniques. A first technique consists in systematically reproducing the chosen processing operation. It is then commonplace for the bit value of one of the neighbours of the current element to be tested a plurality of times during processing. A second technique proposes to remedy this problem by providing, after each test of an element of the neighbourhood, two tests of another element of the neighbourhood. These two tests respectively correspond to the bit values “0” and “1” of the element tested beforehand. The number of tests to be carried out thus substantially amounts to the number of elements to be taken into consideration in the neighbourhood. However, the number of tests to be provided increases as 2
n
as a function of the number of elements n.
Tests of the aforementioned type are often carried out using computer programs. The programs which apply the first technique have a small number of instructions, but require particularly long execution times. Conversely, the programs which apply the second technique have satisfactory execution times, but comprise on average one instruction per test provided, and may reach prohibitive lengths, which tends to increase the processing workload.
OBJECT OF THE INVENTION
It is an object of the present invention to improve the situation.
SUMMARY OF THE INVENTION
The invention is therefore based on a device for processing acquisition data, comprising:
a) a first memory area for storing a sequence of acquisition data, in the form of sequence elements, each having at least one bit;
b) a second memory area comprising a module for access to the first memory area, which can be addressed in order to access the neighbourhood of a designated current element;
c) a third memory area for storing a calculation module, capable of receiving as input a designation of at least one current element, in order to deliver as output to the said neighbourhood of this current element a result word representative of the application of a chosen processing function, this module comprising a set of instructions, with test instructions, each relating to one bit, and forming, from an input instruction, paths where the test instructions are relayed to reach final instructions defining the result word, bit by bit; and
d) control means for repetitively implementing this module in cooperation with a working memory, on the basis of successive current elements, in order to obtain a multiplicity of result words, representing an at least partial transform of the sequence by the said processing function.
According to the invention, the calculation module is provided with an instruction set optimized by a technique of reducing the binary decision tree associated with the said function, in order jointly to minimize the total number of test instructions accumulated over all the paths defined by the test instruction set, and the total number of instructions in this set. Thus, the processing speed is increased by a better compromise between the total memory occupancy of the instruction set and its execution rate.
In a preferred embodiment of the present invention, each test instruction has a conditional branch instruction to go to another test instruction or a final instruction, as a function of the bit which is tested, and the module has at most two final instructions in the memory area. Advantageously, the test instruction set accesses a bit of an element in the neighbourhood at most only once during execution, while the test instructions are relayed, during execution, to one of the two final instructions, designed to designate a result variable representative of one bit of the result word.
According to one of the advantageous characteristics of the invention, the test instruction set has test instructions with inverting branch instructions, while each bit of the result word is defined in correspondence with the associated result variable and a parity of the number of inverting branch instructions taken during execution.
REFERENCES:
patent: 4606066 (1986-08-01), Hata et al.
patent: 4807297 (1989-02-01), Hosoda
patent: 5204752 (1993-04-01), Yamakawa
Malandain Gregoire
Robert Luc
Inria Institut National de Recherche en Informatique et en Autom
Rabin & Berdo P.C.
Tung Kee M.
LandOfFree
Device for processing acquisition data, in particular image... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device for processing acquisition data, in particular image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for processing acquisition data, in particular image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861300