BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows the system logic of the preferred embodiment.
FIG. 2 illustrates the translation function performed by the accumulating memory.
FIG. 3 sets forth the orientation function performed by the accumulating memory.
FIG. 4 defines the logic combining network.
FIG. 5 shows examples of enlarging and reducing of scale control 3 set forth in FIG. 1.
FIG. 6 depicts data path control.
FIG. 7 shows examples of image manipulation.
FIG. 8 sets forth the detailed logic of the accumulating memory and address control 15.
FIG. 9 sets forth the detailed logic of logic unit 11.
FIG. 10 sets forth the detailed logic of unity scale control with connections for enlarge and reduce features.
FIG. 11 shows the detailed logic of the enlarger 7.
FIG. 12 depicts the detailed logic of reducer 9.
FIG. 13 exhibits the detailed logic of clocking and control network 21.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring now to FIG. 1, there is shown a system architecture for the image manipulating apparatus. The M .times. N array of image points, hereinafter termed the "base image" is stored in accumulating memory 15. This memory may be of the bit addressable type in order to facilitate the extraction of subarray geometries anywhere within the array field. In this invention, the subarray geometry of interest is limited to rectangles.
A logic combining unit 11 facilitates the execution of logical operations upon one or more bit streams simultaneously applied thereto over paths 6 and 17. The output from the logical combining unit, also in bit serial form, is applied in parallel to raster output sink 31 and accumulating memory 15 over path 13.
Raster input source 1 driving binary sequences over path 5 through scale control 3 is responsible for the appearance of the bit stream on path 6. A clocking and control unit 21 responsive to a set of parameters applied to it over path 33 regulates the activation/deactivation, synchronism, and addressing of the raster information stored in accumulating memory 15.
The manipulations which the apparatus is capable of performing include translation, orientation, combination, scale change, and input/out. Translation is taken to be the extraction and placement of fields at specific locations in the master array. Orientation includes both the placement of image fields in the master array at any one of four 90.degree. angle rotations and the forming of mirror images in either the horizontal or vertical. Combination refers to the merging of two image fields in any of 16 possible ways. The ability to scale change means that the size of an image field can be altered by an integer ratio. Lastly, input/output implies that image fields can be entered from a raster input source or extracted and applied to a raster output sink.
It is apparent by delimiting the class of images to black/white images, there is a substantial reduction in the amount of memory storage because only one bit per pel, rather than several bits per pel, is required to encode each element. Also, the areas extracted from the array are limited to rectangular subarray geometries. These rectangular subarrays will be referred to as "image fields." As is apparent, rectangular subarray geometry greatly simplifies the accessing of the pels within the field in view of the fact that the Cartesian coordinates of the edges remain constant. In contrast to the random access of the image field within the master array, the pels are accessed sequentially within the subarray geometries. Consecutive pels are called the "scan line." Also within the image fields, scan lines are accessed sequentially. This limitation permits pels to be addressed by incrementing simple counters. Apparatus for performing image manipulation processes a single field at a time, rather than processing several fields at once. This constraint avoids the requirement to multiplex the scan lines from several fields into a single scan line for the master array. The apparatus of the invention is also constrained in that the pels from any manipulation process fall on raster points, rather than permitting them to fall between raster points. This mapping avoids the need for interpolation logic. However, this limit restricts any enlarging and reducing to integer ratios, as well as requiring rotation to be in 90.degree. increments.
Referring now to FIG. 2, taken together with FIG. 1, there is shown the translation function performed by the accumulating memory. In this regard, translation is controlled by the four parameters X, Y, dX, dY. The first picture element of an incoming image field is placed at the starting coordinates X,Y. The size of the image field as modified by the scale control 3 is determined by the parameters dX and dY, where dX gives the extent in the X direction of the image field and the accumulating memory, and dY gives the extent in the X direction.
Referring now to FIG. 3, there is shown the orientation function performed by the accumulating memory. The orientation is controlled by three parameters. These are, namely, F, sX, sY. F designates the coordinate direction which is to be incremented first as the sequential picture elements are received, thereby specifying the coordinate along which the scan line will be. The parameter sX gives the sign for incrementing the X coordinate as either a plus or minus 1. The parameter sY performs the same function for the Y coordinate. FIG. 3 illustrates how the result would appear in the accumulating memory if the incoming image field contained the letter F. The sequence of pels for the incoming image field are always treated as though they were left-to-right, top-to-bottom. In matrix terminology, this is defined as "row major order." In FIG. 3, the orientation change is relative to those scan directions because there can be no absolute coordinates for the incoming image field. Its only reference is the picture element sequence.
Referring now to FIG. 4, there is shown the symbolic definition of logic combining network. The logic unit combines two image fields, picture-element by picture-element. The process used for the combination is specified by the Boolean function parameter B since the two black/white fields are treated as two 2-valued data streams. In the preferred embodiment, the combining process is performed by pure combinatorial logic so that there are no timing considerations other than those of insuring that the corresponding pels from the two images be presented at the same time to the network. As a result, the output is available later after some appropriate circuit delay time. The output can be replaced in the accumulator memory 15 or applied to output sink 31.
Output sink 31 preferably may consist of a presentation device such as a raster printer or display. Also, the sink must be able to accept data with a rate faster than the maximum data rate of the apparatus so as to tolerate variations in data flow and avoid the need for internal buffering on any of the major data paths 5, 6, 17, and 13.
Input source 1 contemplates raster scanners and raster generators of encoded alphanumeric and vector graphics data. The input source 1, similar to sink 31, must be operable at a data rate greater than the maximum data rate of the apparatus.
Scale control 3 changes the size of the incoming image. The size can be enlarged, reduced or left the same. Because of the constraint that any processed picture element must fall on a pel position, enlarging or reducing is equivalent to multiplication and division by integer values. Scale control can be inserted in the output leg, such as in path 13 as an alternative to the input leg on path 5.
Referring now to FIG. 5, there are shown examples of scale change. In enlarging, one picture element is made into many. Because it is impossible to create information that does not exist in the original image, all of the resulting picture elements are given the same value as the original pel. In the reducing operation, several picture elements are logically combined to just one. Reduction is the process for discarding information. Consequently, care must be exercised to preserve as much useful information as possible.
In the scale control operations exemplified in FIG. 5, the control is responsive to parameters SC, R-1 and R.sup.2. The parameter SC determines whether the scan control enlarges, reduces, or preserves the existing size. In the instant case, the scale change is constrainted to be the same in both the x and y directions. The parameter R-1 is one less than the size ratio and is used wherever unity scale is not preserved. The parameter R.sup.2 is the ratio of areas and is used to determine when more than half of the picture elements are black during reduction. It is not used for either enlarging or unity scale.
Both enlarging and reducing involve storing data. In enlarging, data is stored as it comes into enlarger 7 so that it can be replicated. In enlarging, data is read out faster than it is read in. During the time when scan lines are being replicated, no data is being read in, causing thereby an interruption in input data flow.
In the reducing operation, all of the scan lines that will be reduced to a single scan line are read in before any data is read out. Thus, the stored data is processed as the reduced scan line is produced, before any more data is read in causing thereby an interruption in input data flow.
Clocking and control element 21 sets up an operation by initializing each of the units as, for example, input source 1, scale control 3, accumulating memory 15, logic unit 11, or output sink 31. It conditions the input and output it required, and controls the data paths 5, 6, 17 and 13. Clocking and control thereupon gates the master clock so as to allow the operation to proceed. Sufficient intelligence is provided for clocking and control to determine whether the pel clock during each scan line, scan clock at the end of each scan line, or raw clock should be distributed to the elements involved in the operation. Clocking and control also monitors the progress of the operation and signals the completion to the instruction source interface when the operation is completed.
Referring now to FIG. 6, there is shown examples of data path control exercised by clocking and control element 21. Relatedly, the selection of images to be processed and the data paths are determined by the parameters PC, IA, OA. The parameters IA and OA are the input address and the output address respectively. The two bits of the path control parameter PC specify whether the input or output have been selected. Since there are two images processed by the logic unit, one must always be from the accumulating memory, while the other is from the input. However, if the input is not selected, then that leg 6 of the logic unit is forced to 0. If the output 31 is selected, then the image is not replaced in the accumulating memory 15.
Referring again to FIG. 1, all of the parameters are entered over path 33 into clocking and control element 21. The source of parameters may be either a computer or an operator-driven keyboard. Since the size of the image area, as well as any reduction involved, affects the time it takes to perform an operation, then the parameter source must be prepared to supply parameters as needed. In the preferred embodiment, all of the parameters are presented in parallel under the control of two timing lines.
The foregoing paragraphs have been directed to some of the functional aspects of the embodiment. The following paragraphs are directed to illustrate the operation of the apparatus for raster image manipulation. Reference should be made to FIG. 7 which illustrates an example of image manipulation. The objective of the sequence is to take a page of text that has been previously converted to raster form and stored so as to be available to the apparatus at input address 1. The page of text consists of two columns where each row of text is represented by a short line in FIG. 7. A portion of the left-hand column is to be extracted, rotated 90.degree. counterclockwise and placed on the left-hand side of a new page. A diagram that has previously been stored at input address 2 is to be reduced by a factor of two, rotated ninety degrees counterclockwise and placed on the right-hand side of the new page. Fur purposes of this example, it is desired that the diagram would look better switched right-for-left, so a mirror image is created before it is placed on the page. The size of the accumulating memory is assumed to be 1024 .times. 1320 picture elements. The coordinates are given with increasing X to the right and increasing Y down the page. The accumulator memory 15 is cleared before the sequence starts. However, since the first step is a full load of the accumulator memory, its initial status is not important. In this regard, FIG. 7 shows the accumulator memory before and after each operation. The memory after one step is identical to the accumulator before the next step.
The status of the source 1 and output 31 are shown when they are involved in the step. It should be noted that the value of each parameter required for a step is also listed. Parameters which are not included are not used in the step.
Step 1: The accumulator is loaded (B=3) from the input (PC=01) address 1(IA=1) in a raster image storage device (not shown). The input image is the same size as the accumulator memory 15(dX=1024, dY=1320), so that no scale change is required (SC=1). The loading starts in the upper left-hand corner (X=1,Y=1) and proceeds in row major order (F=0,sX=0,sY=0).
Step 2: A portion of the left-hand column of text is extracted from the accumulator memory 15. The area involved is shown in the doted lines in the "before" accumulator memory column. The process starts at (X=90,Y=275) and covers the area (dX=400,dY=840). The normal sequence is followed (F=0,sX=0,sY=0). The area is extracted (B=5) and sent to the output (PC=10) storage address 3(OA=3) to temporarily hold this intermediate result for use in step 4.
Step 3: The whole data memory 15 is cleared by setting it equal to 0(B=0). No input or output is involved (PC=00). The process starts in the upper left-hand corner (X=1,Y=1) and continues for the full area of the accumulator memory (dX=1024,dY=1320). In the normal sequence (F=0,sX=0,sY=0). Although the process could have started in any corner and have progressed in an appropriate sequence, the normal sequence is chosen for convenience.
Step 4: The partial column of text temporarily stored in step 2 is now loaded (B=3) from input (PC=01) storage address 3(IA=3). The size of this field is the same size as the one extracted (dX=840,dY=400). However, the coordinates are reversed because it is rotated as it is placed in the accumulator memory 15. The rotation is achieved by scanning along Y(F=1) in the negative Y direction (sY=1). Successive scan lines are placed in increasing X positions (sX=0). The partial column of text is placed in the proper location by starting at (X=100,Y=1190). The size is not changed during input (SC=1).
Step 5: The diagram is loaded from the input (PC=01) storage address 2 (IA=2). It is reduced to one-half size (SC=0,R-1=1,R.sup.2 =4) as it is loaded. For variety, it is decided to logically OR (B=7) the incoming data with that existing in the accumulator memory. However, since that area of the accumulator memory is presently all zeros, the result is the same as a replace (B=3). The incoming image is the same size as the accumulator memory that is reduced by a factor of two so that the size of the field in the accumulator memory is (dX=660,dY=512) where the reversal of coordinates is caused by the rotation.
Rotation requires that scanning take place along the Y coordinate. Also, the mirror image is produced by scanning to increasing Y(SY=0) while successive scan lines are placed in increasing X positions (SX=0). Lastly, the appropriate starting location is X=100,Y=140.
Referring now to FIG. 8, there is shown a detailed logic diagram of the accumulating memory 15 and the associated address control. The parametric inputs F, Y, sY,X,sK are supplied by control logic element 21 over collective path 19 to corresponding y and x counters through appropriate control logic activated by pel and scan clocks from clocking and control unit element 21. The accumulating memory includes a random access bit addressable memory 81 for storing data serially by bit applied to it over path 13 and for supplying data serially by bit out over path 17. The X and Y coordinates are applied to address register 83 from the corresponding x and y counters 85 and 87. The counters, themselves, are of the up/down type with synchronous loading.
The memory is initialized by loading X and Y values into counters 85 and 87, respectively. Parameters F, sX,sY are held at a constant value all through the operation. It should be observed that the pel clock activates memory timing element 89, which element controls the read cycle during phase 1 of pel clock and the write cycle during phase 4. The scan clock operates to gate appropriate parameters from element 21 to counters 85 and 87 for the purpose of either loading, incrementing or decrementing the register count.
After initialization, in response to each pel clock pulse received over path 91, memory 81 is first read and then written into at the current address contained in register 83. Additionally, the contents of registers 85 and 87 are changed as a function of the parameters in F,sX, and sY.
If F=0 and sX=0, then the x count in register 85 is incremented by phase 5 of the pel clock. If F=0 and sX=1, then the x count is decremented by phase 5. Likewise, if F=1 and sY=0, then the y count in register 87 is incremented by phase 5, while if F=1 and sY= 1, then the y count is decremented by phase 5.
When a scan clock pulse is received over path 93, then the registers 85 and 87 have their contents altered as a function of F,sX and sY, as follows:
If F=0, and sY=0, then the x count is loaded in register 85 and the y count is incremented by phase 5. If F=0 and sY=1, then the x count is loaded and the y count is decremented. If F=1 and sX=0, then the y count is loaded and the x count incremented. Lastly, if F=1 and sX=1, then the y count is loaded and the x count is decremented.
Referring now to FIG. 9, when taken together with FIG. 4, there is shown a logic unit 11 to which serial data from the scale control element 3 is applied over path 6 and serial data from the accumulator memory 15 is applied over path 17. The output of the logic unit is applied to data path 13.
Logic unit 11 can have its function configured by the signals applied to the plurality of conductors B.sub.8, B.sub.4, B.sub.2, and B.sub.1 shown as control path 23 running from clocking and control element 21.
For example, if the control leads B.sub.8, B.sub.4, B.sub.2, B.sub.1 are coded as 0111, then the logic unit represents a logical "OR": If the control leads are coded as 0110, then an exclusive "OR" is set up, etc. Other control combinations include 0001 for a logical "AND," 0011 for "replace," 0101 for "extract," 0000 for "set to 0," and 1111 "set to 1's."
Referring now to FIGS. 10-12, there is shown the detailed logic level embodiments of scale control element 3 of FIG. 1. More particularly, FIG. 10 sets forth the detailed logic of unity scale control with connections for enlarge and reduce features. FIG. 11 shows the detailed logic of the enlarger 7, while FIG. 12 depicts the detailed logic of reducer 9. As previously mentioned in discussion with FIG. 5 showing examples of scale change, there are three paramenters regulating scale control operations. These parameters are, respectively, SC, R-1 and R.sup.2. The parameter SC determines whether the scan control enlarges, reduces or preserves the existing size. Parameter R-1 is one less than the size ratio and is used whenever unity scale is not preserved. Lastly, the parameter R.sup.2 is the ratio of areas and is used to determine when more than half of the picture elements are black during reduction. It is not used for either enlarging or unity scale.
Parametric control is supplied from clocking and control unit 21 to scale control element 3 over path 25.
Referring now to FIG. 10, the input pel clock from enlarger scale control of FIG. 11 is supplied to path 2 and through an AND/OR cluster to raster input source 1 over path 14. Other clocking control includes the pel clock on path 25 applied to latching element D. Since unity scale implies no change in the image, it amounts to a resynchronizing opportunity and a convenient connecting point for the bit streams from enlarger 7 over path 12 and reducer 9 over path 10, all of the foregoing being coupled to the logic unit 11 via path 6.
Referring now to FIG. 11 there is shown enlarger 7 responsive to raster input source over path 5 and generating an output over path 12 which terminates in the unity scale element described in FIG. 10. Since parameter SC determines whether to enlarge or reduce, if selected, the enlarger parameter is regulated by R-1 shown driving a scan counter. As suggested in enlarging, data must be read out on path 12 faster than it is read in on path 5. This derives from the fact that enlarging consists of replication of picture elements by an integral number of times. The input data is stored in temporary store so that scan lines can be replicated an integral number of times. During scan line replication, no input is taken into the enlarger. The enlarger is enabled over path 25 by the same AND gate logic that terminates the pel clock and the scan clock. A scan counter and pel counter regulated by parameter R-1 control the replication.
Referring now to FIG. 12, there is shown the reduced scale control 9. Scale reduction proceeds in two steps. First, R scan lines are loaded into temporary store, one scan line at a time. The loading proceeds by reading the contents of the memory into the temporary store data register. The input data is inserted into the bit position determined by the scan count directed to the bit select. Then the modified temporary store data register is written into the temporary store. During this period, the pel clock is inhibited. The pseudo pel clock is used to count the pels in the reduced scan line by decrementing DP in FIG. 13. The relation of input pels to reduced pels is maintained by the pel count. At the end of each scan line, the pseudo scan clock is used to restore the counting of pels in the reduced scan line by loading DP in FIG. 13, but it does not decrement DS in FIG. 13 because the reduce element has not yet produced the reduced scan line. This process is continued until the scan count is decremented to zero.
The second step actually generates the reduced scan line. Before each group of R.sup.2 pels are examined to determine whether a black or white output pel should be produced, the black count is loaded with R.sup.2. Then, one pel from each of R scan lines is read from the temporary store into the count register. In the count register each pel in sequence is shifted into the left-hand position where, if it is a black pel, it enables the black count causing it to be decremented by 2. After R groups of R pels have been examined, the contents of the black count is compared to zero. If the black count is less than zero, a black pel is placed on output pel line 10; if greater than zero, a white pel is placed on output pel line 10; if equal to zero, then a pel value opposite to the current pel value is placed on output pel line 10. This process continues until a reduced scan line is produced, at which time the counter DS in FIG. 13 is decremented. The above process is repeated until all scan lines in the input image have been processed as indicated by counters DS and DP, FIG. 13, being decremented to zero.
State Decode Table for FIG. 12
I = initialize
L1 = (mode = 00) & (pel count .noteq. 0) & (DP .noteq. 0) & raw clock
L2 = (mode = 00) & (pel count = 0) & (DP .noteq. 0) & raw clock
L3 = (mode = 00) & (scan count .noteq. 0) & (DP = 0) & raw clock
L4 = (mode = 00) & (scan count = 0) & (DP = 0) & raw clock
R1 = (mode = 01) & (scan count = 0) & (pel count = 0) & raw clock
R2 = (mode = 10) & (scan count .noteq. 0) & raw clock
R3 = (mode = 10) & (scan count = 0) & (pel count .noteq. 0) & raw clock
R4 = (mode = 10) & pel clock
R5 = (mode = 01) & scan clock
L1+l2 = (mode = 00) & (DP .noteq. 0) & raw clock
L3+l4 = (mode = 00) & (DP = 0) & raw clock
Referring now to FIG. 13, there is exhibited the detailed logic of clocking and control network 21. Parameters F, dY, dX, PC and SC are applied over paths 33. It is through this interface that all parameters are entered. The other function of this element is that of providing clocking and synchronizing signals to be distributed to all elements in the system; so that given a master clock, submultiple frequencies of interest can be derived and transmitted. Thus, raw clock is gated through from the master clock while the pel clock, scan clock are derived submultiples and transmitted over paths 25 and 19.
Decode Table for FIG. 13
Select Input = (PC = 01+11) & (Start Op.+Op. Busy)
Select output = (PC + 10+11) & (Start Op.+Op. Busy)
Enable Reduce = ((PC=01+11)&SC=01) & (Start Op.+Op. Busy)
Enable Enlarge = ((PC=01+11)&SC=10) & (Start Op.+Op. Busy)
Enable Unity = ((PC=01+11&SC= 00) & (Start Op.+Op. Busy)
Clocking and control circuit 21 sets up the manipulation operation when signalled to do so. In terms of signal flow, it selects the signal source and notes input ready when received. It selects the sink and notes the output ready when received. Clocking and control further initializes the accumulating memory 15, the enlarger 7 and the reducer 9. In performing the operation, the clocking and control circuit sends the pel and scan clock to those units involved.
It should be appreciated that the pel clock provides a cycle for each pel read from the accumulating memory 15. Many events occur for each pel clock cycle. Thus, the pel clock consists of five phases in order to allow for the circuit delays involved in the events which occur in a single pel clock cycle. The pel clock is shown in the diagrams as though it were a single phase except the phase used by various units, for example, .phi..sub.2 is shown at the pel clock input to the unit in FIGS. 8, 11 and 12. Relatedly, the scan clock cycle occurs at the end of each scan line. There is no data transfer. The scan can be along either the X or the Y direction in the accumulating memory 15 depending upon which coordinate is sequenced first. Since there is only a reinitialize function performed by the scan clock, it can consist of a single phase. Also, it should be noted that a pel clock can be inhibited by the reduced function, if selected. When reducer 9 is selected and the pel clock inhibited, then clocking and control network 21 sends "raw clock" to the reducer unless the conditions for scan clock exist. In the latter case, scan clock is sent unless scan clock is inhibited in which case raw clock is again transmitted. The assumption is that once conditions are present to initiate a clock cycle, then all phases will be produced even if the initiating conditions cease in the middle of the cycle.
The foregoing has described the system of this invention and has illustrated its concrete implementation. It is a matter of course that known circuits are selectively employed as the circuits of the above described block diagrams by those skilled in the art. It is needless to exemplify the detailed logic. Such circuits may be those shown, for example, in "Pulse, Digital, and Switching Waveforms, Devices, and Circuits for their Generation and Processing," Sections 18, 9 and 10, by Jacob Millman, Herbert Taub, published by McGraw Hill Book Company.
It will be apparent that many modifications and variations may be affected without departing from the scope of the novel concepts of this invention.