Abstract:
Image data is transposed between successively arranged first data points in a first image field and successively arranged second data points in a second image field by a method comprising: (1) successively specifying a first data point (i); (2) summing first control data indicative of a residue with second control data indicative of a constant value; (3 1 ) if the result of the summation does not exceed a predetermined value, updating the first control data with the summation result and specifying a second data point (j) corresponding to the specified first data point, or (3 2 ) if the result exceeds the predetermined value, subtracting it from the summation result to update the first control data with the residue, and specifying a second data point (j) which is shifted by one data point with respect to the specified first data point; (4) transferring the image data from the specified first data point to the specified second data point or from the specified second data point to the specified first data point depending on the relative size of the first and second image fields. The steps (1) to (4) are repeated until all the second data points are filled with the image data.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates generally to data processing systems, and in particular to a logical image controller in which logical operations are performed upon two-valued image signals to provide scaling of an original image to a desired size and rotation of the image to a desired angular position 
     With the extensive use of microcomputers in various fields of businesses, demands have been arisen to scale up or down or rotate a video image on the screen of a data processor at high speeds. To derive the location of pixels of the image on a destination field the usual practice is to employ a method known as the Affine conversion matrix in which a desired scaling ratio is multiplied upon a line segment on which pixels of the source image field are located. However, this requires multiplication operations to be performed upon each pixel of the original image field. Since multiplication operation involves a large number of computation steps, it takes longer to process all the binary image signals of an image field 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the present invention to reduce the amount of time involved in processing image data for conversion of image size and orientation. 
     This object is obtained by the use of sum and subtract operations instead of multiplication operation. 
     The present invention provides a method for processing image data by transposition between successively arranged first data points in a first image field and successively arranged second data points in a second image field. The method comprises the steps of: 
     (a) successively specifying a first data point; 
     (b) summing first control data representing a residual value with second control data representing a constant value; 
     (c) (c 1 ) if the result of the summation does not exceed a predetermined value, updating the first control data with the result of the summation and specifying a second data point corresponding to the specified first data point, and (c 2 ) if the result exceeds the predetermined value, subtracting same from the summation result to update the first control data with the residual value of the subtraction, and specifying a second data point which is shifted by one data point with respect to the specified first data point; 
     (d) transferring the image data from the specified first data point to the specified second data point when the first image field is greater in dimension than the second image field, or transferring the image data from the specified second data point to the specified first data point when the first image field is smaller in dimension than the second image field; and 
     (e) repeating the steps (a) to (d) until all the data points to which the image data are to be transferred are filled with image data bits. 
     The present invention further provides an apparatus for processing image data by transposition between successively arranged first data points in a first image field and successively arranged second data points in a second image field. The apparatus comprises: 
     first means for generating a clock pulse; 
     second means responsive to the clock pulse for summing first control data of a residual value with second control data of a constant value and if the sum exceeds a predetermined value subtracting the predetermined value from the sum and renewing the first control data with the residual value of the subtraction; 
     third means having storage locations defining the first data points for storing therein the image data and shifting the stored image data therealong in response to the clock pulse in a first direction when the first image field is greater in dimension that the second image field and in a second direction when the first image field is smaller in dimension that the second image field; and 
     fourth means having storage positions defining the second data points connected to the third means for storing and shifting the image data therealong in response to the sum exceeding the predetermined value in the first direction from the third means to the fourth means when the first image field is greater in dimension than the second image field and in the second direction from the fourth means to the third means when the first image field is smaller in dimension than the second image field 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will be described in further detail with reference to the accompanying drawings, in which: 
     FIGS. 1a, 1b and 2 are illustrations useful for describing the underlying principle of the present invention; 
     FIG. 3 is an illustration of a hardware embodiment of the present invention; 
     FIG. 4 is an illustration of a software embodiment corresponding to the FIG. 3 embodiment, and FIG. 4a is a modification of FIG. 4 which is employed when the original image field is scaled up; 
     FIG. 5 is an illustration of a modified embodiment of FIG. 3; 
     FIG. 6 is an illstration of a flow chart corresponding to the hardware embodiment of FIG. 5; 
     FIG. 7 is an illustration useful for describing a feature of the present invention; 
     FIG. 8 is an illustration of a hardware block diagram embodying the feature of FIG. 7; 
     FIG. 9 is an illustration of a software version of FIG. 8; 
     FIG. 10 is an illustration of the principle of rotation by which the orignal image field is rotated to a desired location; 
     FIG. 11 is an illustration of a hardware embodying the principle of FIG. 10; 
     FIG. 12 is an illustration of a software version of FIG. 11; and 
     FIGS. 13-16 are illustrations of a microprocessor embodying a high speed processing feature of the present invention. 
    
    
     DETAILED DESCRIPTION 
     Before going into the detail of the present invention it is appropriate to discuss the principle underlying the present invention with reference to FIGS. 1a and 1b. Consider first that a selected region of an image displayed on the screen of a cathode ray tube is scaled up or down with a desired ratio m/n. Each of the pixels on the screen image is represented by a binary 1 or 0 and located at the intersection of a row and a column of a square matrix to make it compatible with the row-column format of a frame memory to be described. It is assumed that a set of eight original binary image data a i  (i=1 to 8) representing the image densities of pixels on a row 1 is scaled down with a reduction ratio of 5/8 to a set of five binary image data b j  (j=1 to 5) arranged on a row 2, as shown in FIG. 1a. For purposes of simplicity the lattice interval is assumed to be unity for the moment. 
     The pixel location is represented by the system of coordinates and if the row number is known, each pixel is identified by an integral number representing the column on which it is located. Any fractional number which is derived in the process of computation is stored as a &#34;residue&#34; in a register. In FIG. 1b, the original image data a 1  to a 8  are arranged on the abscissa of a coordinate system and the scaled-down image data b 1  to b 5  are on the ordinate. A solid line 3 has a slope ratio of 5/8 which corresponds to the reduction ratio and dots S 1  to S 8  are located at intersections which are closest to the conversion slope 3 measured in a direction parallel to the ordinate. 
     Subscript j represents the output pointer of a memory system to be described and is a function of the input pointer i as given by the following relation: 
     
         j(i)=[(m/n)(i-1)+Ro]                                       (1) 
    
     where, i=1, 2, . . . , n, j=1, 2, . . . , m, and if Ro=m/2n, ##EQU1## Therefore, Equation 2 is written as: 
     
         j=[(5/8)(i-1)+5/16]+1                                      (3) 
    
     The dotted line 4 in FIG. 1b represents Equation 3 and the solid line 3 is represented by the following equation: 
     
         j=(5/8){(i-(1/2)}+1/2                                      (4) 
    
     An initial value m/2n (=5/16) is first reset into the register as the &#34;residue&#34; when the pointer i is 1 and the j pointer is set to 1. In response to the i pointer being incremented to 2, the scale down ratio 5/8 is added to the initial value of residue 5/16 to give a total of 15/16 and the j pointer remains unaltered. The same scale down ratio 5/8 is added each time the i pointer is incremented. When the total value exceeds &#34;1&#34;, a carry signal of the unity value &#34;1&#34; is overflowed from the register, reducing the total value stored therein to 9/16 when the i pointer is incremented to 3, and the j pointer is incremented to 2. Thus, the j pointer remains unaltered when the register content is smaller than unity and is incremented when the unity value is exceeded As the above process is repeated, the register is overflowed when the i pointer becomes equal to 3, 4, 6 and 7 and the j pointer is incremented in response thereto as illustrated in FIG. 2. 
     FIG. 3 is a schematic illustration of the internal structure of a microprocessor according to an embodiment of the present invention. The embodiment comprises a residue register 10, a setting means 11 for setting an initial residue Ro to the register 10, and an adder 12 which forms part of the arithmetic logic unit (ALU) of the microprocessor. 
     To generalize the concept of the present invention, the lattice interval is represented by a quantity L which is in turn represented by L stages of the residue register 10. An increment register 13 stores a constant C which equals (m/n)L, this value being applied to the adder 12 and summed with a value R stored in the register 10, giving a total R+C. This total value is fed back to the register 10. 
     The residue register 10 is triggered in response to input pulses supplied from a clock source 14 through a gate 15 which is gated on in response to an output signal from a flip-flop 16 whose setting input is activated by an EXECUTE key, not shown, of a keyboard and whose resetting input is connected to the output of a programmable counter 17. This counter 17 is arranged to be cl.eared in response to the operation of the EXECUTE key and takes its input from the gate 15 to count the clock pulse until a value T is reached which indicates the number of pixels contained in the selected image area and is preset by a command signal from the keyboard, so that gate 15 is open for an interval corresponding to the preset value T. 
     A frame memory 18 stores binary image signals from a desired area of a display 19 for successively feeding an input register 21 through a switching means 20 with image signals on successive rows in response to the end of reduction operations performed upon each row. The input register 21 includes a plurality of storage locations which defines source data points of a first image field on which original image data bits are located and shifted by one bit position to the left in response to a clock pulse from the gate 15 which is applied as the i pointer. The shifted image data a i  is applied in succession to an output register 22 which includes a plurality of storage locations defining destination data points of a second image field to which input image data a i  is transferred. 
     In response to each clock pulse, the register 10 is loaded with the sum R+C from the adder 12. When the stored total value exceeds the maximum value L, a carry signal is overflowed from the register 10 and the value L is automatically subtracted from the stored value, leaving a fractional number R which is fed to the adder 12 to be summed with the incremental value C in response to the next triggering clock pulse. 
     The output register 22 is shifted one bit position to the left in response to the j pointer which is applied from a carry detector 23 whenever an overflow occurs in the residue register 10, generating output binary image signals b j  Switch 20 is switched to apply the output image signals b j  to the frame memory 18 to be displayed within an area in the display 19 which is scaled down with a ratio m/n. Upon transfer of the output data b j  to the frame memory, input image signals on the next row are transferred from the frame memory to the input register 21. The above process is repeated until the preset value T is reached in the counter 17. 
     FIG. 4 is an illustration of a flow diagram associated with the hardware version of the present embodiment. A timer count value t of counter 17 is initialized to zero (block 30) and the residue R is initialized to Ro (block 31). The i pointer is incremented by one (block 32) and the residue R is summed with incremental value C in adder block 33. The summed residue is checked against the value L in check block 34 and if R is equal to or greater than L, control exits to a block 35 to subtract L from R and the j pointer is incremented by one (block 36). If R is smaller than L, blocks 35 and 36 are skipped and block 37 is executed by setting a i  to b j . Count value t is incremented by one (block 38) and control returns to block 32 to repeat the above steps 32 to 38 through block 39 until t becomes equal to or greater than the preset value T. 
     Original images can be scaled up in a manner inverse to the scale down process described above. Therefore, in the embodiment of FIG. 3 the original image data is stored in the output register 22 and shifted to the input register 21 in response to a j pointer increment and delivered therefrom in response to an i pointer increment which occurs at regular intervals. In the flow diagram of FIG. 4, it is only necessary that the direction of arrow in block 37 be reversed as shown at 37a in FIG. 4a when image expansion is desired. 
     FIG. 5 is an illustration of a pratical form of the FIG. 3 embodiment, wherein parts corresponding to those in FIG. 3 are marked with the same numerals used in FIG. 3. The increment register 13 of FIG. 3 is divided into a numerator register 13a storing a value P which is a product of distance L multiplied by m and a denominator register 13b storing a value -Q which is a product of distance L multiplied by n. Likewise, the adder 12 is divided into a first adder 12a which provides summation of R from register 10 with the numerator P and a second adder 12b which provides summation of R with a denominator -Q. The binary output of adder 12b is applied to a negative detector 24 which provides an output when the result of the summation at 12b is of a negative value to a multiplexer controller 25 which controls first and second multiplexers 26 and 27. These multiplexers are controlled such that the first multiplexer 24 initially applies the output (R+P) from adder 12a to register 10 and subsequently the second multiplexer 25 is controlled in dependence on the output of the negative detector 24. If the summation by the adder 12b results in a positive value, the multiplexer controller 25 applies command signals to the first and second multiplexers to couple the output of adder 12b to register 10. A carry signal is generated from register 10 to increment the j pointer by one. If negative, the output signal from negative detector 24 causes the controller 25 to generate command signals so that the output of register 10 is instead reapplied thereto and no carry signal is generated. 
     FIG. 6 is an illustration of a flow diagram which is associated with the FIG. 5 embodiment, wherein blocks corresponding to those in FIG. 4 are marked with the same numerals as used therein. In block 33a, the residue R is summed with the numerator P and in block 34a control checks if R is equal to or greater than the denominator Q. If R≧P, control exits to block 35a to subtract Q from R and advances to Step 36 to increment the j pointer. If R is smaller than Q, the Steps 35a and 36 are skipped to Step 37 to update b j  with a i . 
     In the previous embodiments, a scale down of a letter T shown at 40 in FIG. 7 is likely to result in a truncation of the stem of the T and a truncation of the arm at opposite ends as shown at 41 if binary 1&#39;s at column a 4  are lost. The truncation problem can be avoided by modifying the hardware embodiment of FIG. 4 in a manner as shown in FIG. 8 in which a supplemental register 45 is connected to the output of the input register 21 to hold the image signal for one bit duration. An OR gate 46 is provided having a first input connected to the rightmost bit position 22a of the output register 22 and a second input connected to the output of supplemental register 45. The output of OR gate 46 is coupled to the rightmost bit position 22a. With this arrangement, a pair of any successive image data bits a i  and b j  are combined in the OR gate 46 to generate a logical 1 if one of the input bits is a binary 1.  The logical 1 from OR gate 46 is loaded into the rightmost bit position of register 22. If b j  is a binary 0 and a i  is a binary 1, the resultant logical 1 from OR gate 46 is loaded into the bit position 22a to alter the binary state of b j  to 1. If a.sub.(i+1) is binary 0 at the next trigger instant, the binary 1 of b j  remains unchanged. Therefore, when the rightmost bit position 22a is filled with data a 1  it is renewed with data a 2  and a binary 1 at 43 is reconstructed at 43&#39; on the column b 1  of the scaled down image 42. Likewise, when the rightmost position 22a is filled with data a 3 , it is renewed as b 3  with a binary 1 of data a 4 , reconstructing binary 1&#39;s on the stem of the letter T the b 3  column. Data a 6  and a 7  are likewise combined to reconstruct binary 1&#39;s at column b 5 . 
     FIG. 9 is an illustration of a flow diagram associated with the FIG. 8 embodiment. This flow diagram is generally similar to FIG. 4 but differs in that it additionally includes a block 51 to store input data a i  into a memory as output data b j  before the i pointer is incremented in block 32 and further includes a block 52 which is performed if the residue R is smaller than L by resetting b j  to the result of logic summation of b j  and a i . The block 37, by which b j  is reset to a i , is exclusively performed after the j pointer is incremented in block 36. 
     FIG. 10 illustrates the principle of another embodiment of the invention which provides rotation of an original image. For the sake of brevity, the original image comprises binary image data al to a 8  which are spaced apart a distance L along a straight line 60 as in the previous embodiments which is rotated by an angle θ so that they are relocated to hypothetical points b 1  to b 8  along a line 61. The hypothetical locations of image data b i  are further relocated to nearby lattice intersections designated c 1  c 7  as follows. 
     The locations of data b i  along the line 61 are represented by coordinates j=X bi  and k=Y bi  : ##EQU2## where, Rxo and Ryo represent the location of b 1  on X-Y coordinates. Data b i  is converted to data c jk  by analogy between Equation 1 and Equations 5 and 6 with the scaling ratio m/n corresponding to cos θ and sin θ. 
     FIG. 11 is a schematic illustration of a hardware of a microprocessor embodying the principle shown in FIG. 10. The embodiment generally comprises an X-residue register 70 and a Y-residue register 71 which are resettable to initial residual values Rxo and Ryo, respectively. The X-residue register 70 has L bit positions whose contents are summed in an adder 72 with a binary signal representing L cos θ from a cosine register 73 and its binary input coupled to the output of adder 72. Likewise, the Y-residue register 71 has L bit positions whose contents are summed in an adder 74 with a binary signal representing L sin θ from a sine register 75 and its binary input coupled to the output of adder 74. Registers 71 and 72 are triggered by pulses from a pulse generator similar to that shown in FIG. 3 and feed carry signals to carry detectors 76 and 77, respectively. 
     Original image data is loaded into an input register 78 in response to the i pointer which is supplied from the clock source 14 and shifted to a random-access memory 79 having a matrix array of storage locations which are addressable as a function of the output of an X-address register 80 and a Y-address register 81 which are respectively arranged to receive the j and k pointers from carry detectors 76 and 77. The address code stored in X-address register 79 indicates the location of image data b i  projected on the X-axis of the coordinate system of FIG. 10, while the address code in Y-address register 81 indicates the location of image data b i  projected on the Y-axis. The image data supplied from the input register 78 is stored into a storage location addressed as a function of the X and Y address codes as an image datum C jk  and read out of the memory 79 to the frame memory 83 by way of a switch 82 and thence to a display 84. 
     The operation of the FIG. 11 embodiment will be better understood with reference to a flow diagram shown at FIG. 12. After initializing steps in blocks 90 and 91 by which t is set to zero and residues Rx and Ry are set to Rxo and Ryo respectively, the i pointer is incremented by one (block 92) and L cos θ is summed with Rx (block 93) in the adder 72. Rx is compared with L and if Rx is equal to or greater than L, control exits to block 95 to subtract L from Rx. Register 70 is overflowed and carry detector 76 increments the j pointer by one (block 96), and control proceeds to a block 97. If Rx is smaller than L, register 70 is not overflowed and control goes to block 97. 
     In block 97, L sin θ is added to Ry and comparison is made between Ry and L (block 98). If Ry is equal to or greater than L, register 71 is overflowed, subtracting L from Ry (block 99) and the k pointer is incremented by one by carry detector 77 (block 100) and control advances to block 101. If Ry is smaller than L, control exits from block 98 to block 101. 
     In response to the j and k pointers, c jk  data bits are stored into RAM 79 (block 101). Timer t is incremented by one (block 102) and the above process is repeated until t becomes equal to or greater than the total number of bits in the original image area represented by T. 
     While conventional general purpose data processors can be employed to implement the software of the present invention for high speed computation of binary image processing, it is preferable to modify the hardware of such processors to further increase their operating speed. 
     In FIG. 13, a portion of the hardware of a conventional microprocessor is schematically illustrated. Machine language instructions are transferred from a main memory 110 to an instruction register 111 over memory bus 112 and internal bus 113. A mapping programmable logic array (MPLA) 114 translates the machine language instructions loaded into the instruction register 111 and transmits the header address of the translated microprogram to a multiplexer 115. A control memory address register (CMAR) 116 temporarily stores address information transmitted from MPLA 114 via multiplexer 115. The address information is utilized by a control memory (CM) to read microinstructions for application to a microinstruction register (MIR) 118. A microinstruction decoder (DEC) 119 decodes the microinstructions stored in MIR 118 to generate command signals TR, GE, TW, CSUB which are applied to a register file 120. An incrementor 121 increments the output of CMAR 116 by one and recirculates the incremented output to CMAR 116 via multiplexer 115 to sequantially address microinstructions stored in control memory 117. Shown at 122 and 123 are A-register and B-register respectively which temporarily store information to be fed to arithmetic/logic unit 124. A carry register 125 stores a carry bit overflowed from the most significant bit position of ALU 124, the carry information being transmitted to the multiplexer 115 and to the register file 120. 
     FIG. 15 illustrates a flow diagram by which the contents of the register file 120 are updated. Parameters C (=Lm/n), L, R are loaded into word registers F1, F2 and F3 respectively from a frame memory, or random access memory 146. Parameter C on register F1 is first transferred to A-register 122. Parameter R on register F3 is then transferred to B-register and the contents of A- and B-registers are summed and the result of the summation (R+C) is replaced to register F3 (block 151). Parameter L on register F2 is transferred to A-register (block 152). Parameter (C+R) is transferred to B-register (block 153). The conditional subtract operation as effected in the steps 34 and 35, FIG. 4, is performed by the hardware given below to reduce the processing time. 
     When conditional subtract instructions are loaded into microinstruction register (MIR) 118, ALU 124 performs a subtrat operation on input data L and (R+C) now stored in A- and B-registers respectively. Due to the provision of a connection 125a from the carry register 125 to register file 120 by which carry bit is transmitted thereto, the result of the subtraction is transferred instantly to the register file in response to the occurrence of the carry bit to permit control to advance to block 36, FIG. 4. 
     In FIG. 14 wherein details of the register file 120 are shown, a carry bit CRY is applied from carry register 125 to an OR gate 130 to which is also applied a conditional subtraction command signal CSUB which is supplied from the decoder 119. The output of OR gate 130 is applied to an AND gate 131. Register write and read timing signals TW and TR are supplied from the decoder 119 to AND gates 131 and 132 whose outputs respectively represent write enable (WE) and read enable (RE) signals. Signal GE indicating that the data stored in the register file 120 is an operand is also applied from the decoder 119 to AND gates 131 and 132. 
     In response to a write enable (WE), transistors 133 and 134 are turned on to cause transistor 135 or 136 to turn on depending on the data bits on bus 113, so that line 137 or 138, which have been held at a logical 1 level by transistors 139 and 140, switches to logical 0 level. 
     A register select signal is applied to an address decoder 141. Assume that a line 142 is brought to a logical 1 level in response to that select signal, transistors 143 and 144 are turned on to store the binary information on the bus 113 into a memory cell 145. 
     Instead of the connection 125a a multiplexer 150 may be provided as shown in FIG. 16 so that it multiplexes the outputs of ALU and B-register in response to the output of carry register 125 coupled by a connection 125b and delivers the multiplexed data to the bus 113. 
     The foregoing description shows only preferred embodiments of the present invention. Various modifications are apparent to those skilled in the art without departing from the scope of the present invention which is only limited by the appended claims. Therefore, the embodiments shown and described are only illustrative, not restrictive.