Binary image processor

• US 3,905,018 A
• Filed: 09/15/1972
• Issued: 09/09/1975
• Est. Priority Date: 06/22/1970
• Status: Expired due to Term

• Current Assignee: Stephen B. Gray
• Original Assignee: Stephen B. Gray
• Inventors: Gray, Stephen B.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/289,326
• Time in Patent Office: 1,089 Days
• Field of Search: 340/146.3MA,146.3H,146.3Q,146.3AQ,146.2 235/177
• US Class Current: 382/308
• CPC Class Codes: G01N 15/00 Investigating characteristics of particles; Investigating permeability, pore-volume or surface-area of porous materials identification of microorganisms C12Q
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/30 Noise filtering
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

An image processing system including a stored program processor especially suited for manipulating two dimensional binary data arrays, each array, for example, representative of an image, for the purposes of measuring basic geometric properties of the arrays, cross-correlating two arrays, and creating new arrays as a function of one or two other arrays. The image processor preferably operates in conjunction with a general purpose central processor unit (CPU) including a random access memory which provides the image processor with both the image data arrays and program commands defining the particular image process or operations to be performed with respect to the data arrays. The defined image process normally involves accessing one or two data arrays from sequential locations in the CPU memory. As the data arrays are being accessed, they are being operated upon to, for example, create a third data array as a function of the first two data arrays, the third data array being stored back into the CPU memory. Concurrently, the three arrays can be measured in various manners with the measurements also being stored in the CPU memory. Means are provided for concurrently performing an additional major processing function involving correlation between the first and second data arrays to, for example, determine the shape similarity and relative positional offset therebetween. Additionally, the image processor is also concurrently able to analyze or measure the third image formed as function of the first two images.

Claims

1. In apparatus for analyzing unknown images represented by binary data stored in a memory, an image processor comprising:

an unknown image data register for holding a plurality of bits comprising a portion of said unknown image data;

a result image data register;

a mask image data register for holding a plurality of bits comprising a portion of mask image data stored in said memory;

means for successively arithmetically comparing the magnitude of corresponding multiple bit bytes in said unknown and mask image data registers for generating a result bit in response to each comparison having a first value when said unknown data byte has a magnitude greater than said mask data byte and a second value when said mask data byte has a magnitude greater than or equal to said unknown data byte;

means for successively entering said result bits into said result image data register;

means for entering successive portions of said unknown and mask image data stored in said memory into said unknown and mask image data registers, respectively; and

means for successively storing in said memory data from said result data register to thereby generate in said memory an array of data representing a result image which is a preselected logical modification of said unknown image.

2. An apparatus for analyzing unknown images in relation to known images, said unknown and known images being represented by respective arrays of binary data adapted to be arranged along first and second axes;

an image processor comprising;

a plurality of unknown image data registers, each including a plurality of bit stages, for holding portions of said unknown data corresponding to successive lines spaced along said first axis;

a known image data register, including a plurality of bit stages, for holding known data corresponding in location within the respective images to one of the held lines of unknown data;

means for entering successive lines of known and unknown data into said known data register and one of said unknown data registers respectively and for entering into each of the other unknown data registers data from a preceding unknown data register in said series;

means defining a set of bit stages within said plurality of bit stages of said unknown image data registers and within said plurality of bit stages of said known image data register;

said unknown image data registers including means for scanning said defined set of bit stages therein in successive blocks, each block comprised of a subset of bit stages, to successively access groups of bits from each register;

said known image data register including means for scanning said defined set of bit stages therein bit by bit in synchronism with the scanning of said unknown image data registers;

means for generating a plurality of correlation signals, one for each bit position within a scanned block of said unknown data, each such correlation signal being a preselectable logical function of the respective bit of the unknown data in the scanned block and the single bit of known image data corresponding to the scanned block position;

a respective counter driven by each of said correlation signals; and

means for reading out data from said counters, whereby the counts, accumulated by said counters as an array of unknown data is scanned, provide indications of the degree of similarity between the known and unknown images.

3. The apparatus of claim 2 including a parameter register storing binary control signals CUM, CUN, and CNM and wherein said plurality of unknown image data registers comprises three such registers and wherein said scanned blocks each includes three bits with the three bits respectively scanned in each register being designated U0, U1, U2 and U3, U8, U7, and U6, U5, U4;

and wherein the scanned bit of said known image data register is designated M; and

wherein said means for generating correlation signals includes a logic matrix for generating signals Delta CC0 - Delta CC8 corresponding to the Boolean expression Delta CCN CUM.UN.M + CUN.UNM + CNM.UN.M for N 0-8.

4. In an apparatus for analyzing an image represented by an array of binary data arranged along first and second axes, an image processor for determining the quantitative effect ( Delta E) of changing the state of each bit on the connectivity of the image, said image processor comprising:

a series of at least three image data registers for holding portions of said array corresponding respectively to successive lines spaced along said first axis, said registers including means for scanning, in successive blocks along said second axis, the data held in said registers, the blocks being of at least three bits extent on each of said axes with each successive block along said second axis being shifted from the preceding block by one bit, there being nine bit positions in each block and wherein the central bit position is identified as U8, a corner bit position is identified as U0 U1 - U7 respectively identify bit positions extending sequentially around the periphery of said block surrounding said central bit position;

means for entering successive lines of said array data into a first of said image data registers and for successively transferring data from said first image data register to a second of said image data registers and from said second image data register to a third of said image data registers;

logic means responsive to each data array block for generating a corresponding second block comprised of bits W0 - W7 where the position of each of bits W0 - W7 in each second block corresponds to the bit position U0 - U7 in a data array block respectively, and wherein W0 (U0 + U7) . U1 W1 (U7 + U0) . U1 W2 (2 + U1) . U3 W3 (U1 + U2) . U3 W4 (U4 + U3) . U5 W5 (U3 + U4) . U5 W6 (U6 + U5) . U7 W7 (U5 + U6) . U7 counter means for counting the number of bits in each second block in a given state to produce a count indicative of said quantitative effect ( Delta E);

threshold means defining a threshold value; and

comparison means for comparing each count produced by said counting means and said threshold value.

5. The apparatus of claim 4 including means for generating a control signal CWN and wherein said logic means includes means for generating a block comprised of bits V0 -V7 where the position of each of bits V0-V7 corresponds in its block to the bit positions U0-U7 in said data array block respectively as defined by the following Boolean expressions:

V0 CWN.R0 + CWN.U0 V1 CWN.R1 + CWN.U1 V2 CWN.R2 + CWN.U2 V3 U3 V4 U4 V5 U5 V6 U6 V7 U7 where R0, R1, and R2 represent bits of an array R of bits corresponding in position to bits U0, U1, and U2 respectively in said data array.

6. The apparatus of claim 4 including means for generating a control signal CON and wherein said logic means includes means for generating bits W0-W7 as defined by the following Boolean expressions:

W0 (V0 + V7) . V1 CON + CON . V0 W1 (V7 + V0) . V1.CON + CON . V1 W2 (V2 + V1) . V3 CON + CON . V2 W3 (V1 + V2) . V3.CON + CON . V3 W4 (V4 + V3) . V5 CON + CON . V4 W5 (V3 + V4) . V5.CON + CON . V5 W6 (V6 + V5) . V7 CON + CON . V6 W7 (V5 + V6) . V7.CON + CON . V7

7. The apparatus of claim 4 wherein said counter means includes nine output terminals and means for providing an enabling signal on the one of said nine output terminals corresponding to value of said count;

said threshold means including means defining a nine bit control signal; and

wherein said comparison means includes logic means for comparing the signal on each of said nine output terminals with the corresponding bit of said nine bit control signal.

8. The apparatus of claim 4 wherein said comparison means includes means providing a single bit output signal P whose state is dependent on whether said count exceeds said threshold value;

and means for logically combining said bit signal P and said bit in position U8 to generate a result bit signal R8.

9. The apparatus of claim 8 including means for generating a multibit control signal BSL;

and wherein said means developing said signal R8 defines different logical combinations of said bit signals P and U8 in response to different states of said control signal BSL.