WO1987003719A1

WO1987003719A1 - Inspection apparatus

Info

Publication number: WO1987003719A1
Application number: PCT/GB1986/000765
Authority: WO
Inventors: Emlyn Roy Davies; Adrian Ivor Clive Johnstone
Original assignee: National Research Development Corporation
Priority date: 1985-12-16
Filing date: 1986-12-16
Publication date: 1987-06-18
Also published as: GB8630026D0; JPS63503332A; GB2184233A; EP0289500A1

Abstract

Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest comprises an edge detector for the positional location of individual articles. The edge detector is fed from a scanner which captures an image of a region in the vicinity of a located article. It analyses the significance of features detected by the scanner and selectively controls the processing of the derived data in order preferentially to obtain data relevant to the features of interest, thereby speeding up processing time.

Description

INSPECTION APPARATUS This invention relates to industrial inspection apparatus and, in particular, to apparatus adapted for the rapid inspection of a plurality of components.

Industrial inspection involves the identification, location, counting, scrunity and measurement of products and components, often under conditions where they are moving at moderate speed along a conveyor system. Products therefore have to be examined in real time, and this imposes a major difficulty, since the processing rate required to analyse the necessary number of pixels is considerably more than can be coped with by a single conventional serial processor. In practice the processing rate is 50-100 times faster than a single central processor unit can cope with so special hardware has to be designed for the purpose.

We have devised an Image-handling Multi-Processor (IMP) for this purpose. IMP consists of a Versatile Modular Eurocard VME bus and crate, which holds a set of special co-procesor boards including a frame store for image processing. The co-processors operate rapidly and enable the system to perform industrial inspection tasks in real time. The system is designed in an integrated way, so that the data transactions on the VME bus give only a limited overhead in terms of speed. In addition, the memory sub-systems are designed to operate at the maximum speed of which the VME bus is capable.

According to the present invention there is provided inspection apparatus for the susccessive inspection of a plurality or articles having a common set of features of interest, comprising detector means for the positional location of individual articles, scanning means to capture an Image of a region in the vicinity of a located article and analysis means to analyse the significance of features detected by said scanning means, wherein selection means coupled to said positional location means is operable selectively to control the processing of data derived from said scanning means in order preferentially to obtain data relevant to said features of interest.

There is also provided an image location device for use in inspection apparatus for the succesive inspection of a plurality of articles having a common set of features of interest, comprising detector means for deriving a plurality of electrical signals corresponding to the intensity of the optical signal at a plurality of positions in the vicinity of a predetermined position on an optical image, combining means for combining pairs of symmetrically- weighted groups of said electrical signals in accordance with a predetermined algorithm to derive a pair of electrical signals dependent on the intensity of the optical signals at positions in the vicinity of said predetermined" position and difference means to derive an electrical signal dependent on the difference between said pair of electrical signals.

The IMP system is built around a frame store typically containing four image-planes of 128 x 128 bytes. The memory is configured so that access is as rapid as VME protocol will allow, viz 150 nsec. A special technique is used to achieve this throughput.

The purpose of the IMP system is to permit industrial inspection tasks to be undertaken in real time and at reasonable expense. Images from a line-scan or TV (vidicon) camera are digitised and fed to the frame store under computer control: they are then processed rapidly by special processing boards. These contain co-processors which operate under control of a host computer and which can access image data autonomously via the VME bus. An arbitrator on the VME bus mediates between the host processor, the image display hardware and the various co-processors. IMP is a multi-processor system to the extent that a number of processors can perform their various functions concurrently, though only one processor may access the bus at any one time. This is not as severe a constraint as might be thought, since (a) pipelining of processes together with provision of local memory enables use to be made of the parallel processing capability of the co-processors; and (b) many real time industrial inspection applications demand speeds that are high but not so high that careful design of the processors will not permit useful tasks to be done by this sort of system. It should be noted that the design of the co-processor system has in this case not only been careful but also ingenious, so that the capability of IMP is substantially greater than that of many commercially available systems, while being significantly less complex and expensive.

The IMP system finds particular application for food product inspection. Considerable numbers of food products have the characteristic that they are round. In our inspection work we needed to ensure that we could locate such products rapidly and then scrutinise them effectively for crucial features and defects. Food products tend to be mass produced in large numbers on continuously moving product lines. These lines are typically 1-2 metres wide, and contain 12-20 products across the width of a conveyor, which may be moving at 30-50 cm per second. Thus the product flow rate past a given point in the line is typically 20 units per second. This means that one processor of the IMP type will have to cope with one item every 50 msec or so. It will have to find each product in the images it receives, and then scrutinise it. An adequate resolution for a single product will be such that the product occupies a square of side 60 to 80 pixels. Thus location of the product is non-trivial, and scrunity is less trivial. It is seen that this sort of problem involves a lot of pixel accesses, but this need not be sufficient to 'tie up' the VME bus and cause data-flow problems.

Considerable attention has heen devoted to the algorithms for locating and scrutinising the product and the types of processor needed to implement them. Although algorithms originally developed for round food product inspection were the first to be implemented in hardware, they have now been generalised so that they are suitable for a much wider variety of products. First, any products which are round or have round holes can be located rapidly and with ease. Second, all such products can be inspected and closely scrutinised. Third, a number of features even of non-circular products can be located directly in their own right, and then products scrutinised in the vicinity of these features, or at related positions. A characteristic of the system is that it relies on recognition of certain features which are capable of triggering the remainder of the system. In our experience, there are a very large number of object features that can simply be located - including holes, specks, dots, characters, corners, line intersections and so on. Thus the IMP system can be used in an extremely wide range of industrial inspection and robotics applications. In addition, there are cases when the object or some feature of it does not need to be located, since its presence and position is already known - e.g. in a robot gripper, at the bottom of a chute, or elsewhere. The IMP system is clearly capable of dealing with this simplified set of situations. Overall, it is seen that the IMP system is in practice of rather general utility. The functions presently performed by the various processors are: (1) edge detection and edge orientation; (2) construction of radial intensity histograms in the vicinity of special features; (3) counting of pixels in various ranges of intensity and with various tags already attached to .them; and (4) correlation of thresholded patterns against internally generated parameters such as distance from the feature of interest. Other features are: (5) construction of angular intensity histograms; (6) construction of overall object intensity histograms, plus (7) construction of intensity histograms within a specified area; and (8) more general grey-scale sub-image correlation. These functions permit the rapid estimatation of product centres, and the measurement of perimeter and area, e.g. that of chocolate cover over a biscuit. A novel feature that permits much of the processing to be carried out rapidly and efficiently is that of autoscan by a particular processor of an area of an image relative to a given starting point, coupled with the use of an internal bus which holds (x,y) and (r,θ) co-ordinates of the currently accessed pixel relative to the starting pixel: this is aided by use of a look-up table on the processor board giving information related to the pixel (x,y) or (r,θ) co-ordinates.

Because the system is designed to use simple functions that can be relocated in the image at will, it is highly flexible and efficient.

In addition to these advantages, the whole system is simply controlled in a high level language from a PDP-11 type of host processor, for which suitable interfaces have been devised. Alternatively, a 68000 or other host processors can be used. The important point here is that complex assembly level programming is not required at any stage. The only requirement imposed by the co-processors is that they should be initialised by RESET signals, that their operation should be started by suitable START pulses, and that certain information should be provided for them in specific registers and memory locations. Data may be read out of them by the host or other processors, or they may write their data to other locations. Control is via a minimal number of registers which may each be given a high level name for programming purposes. The co-processor functions listed above are special functions which have been found to take the bulk of the effort in practical industrial inspection systems. Since these functions are not actually general, they cannot on their own carry out the whole of an inspection task. Thus 'glue' functionality is required between the given functions. This may be provided by the host processor. If this gets slow or is overloaded, then several software co-processors may be added to the IMP system; at present this is envisaged to be possible via DEC T-11 processors, possibly working in conjunction with a bit-slice. It would not be possible for such processors to perform the whole function of IMP because they would operate too slowly for inspection purposes, unless at least 50 concurrently operating processors were added to the system. The IMP system is intended to overcome the need for this sort of solution by doing the bulk of the processing much more economically: thus a brute-force solution is replaced by a clever solution. However, for generality, one or two additional software co-processors form a useful adjunct to the remainder of the hardware. An embodiment of this invention will now be described by way of example with reference to the accompanying drawings in which:-

Figure 1 is a schematic view of an image-handling multiprocessor system;

Figure 2 is a schematic drawing of Processor II from the IMP system of Figure 1;

Figure 3 is a schematic drawing of Processor Module A for Processor II;

Figure 4 is a schematic drawing of Processor Module B for Processor II; Figure 5 is a schematic drawing of Processor Module C for Processor II;

Figure 6 is a schematic drawing of Processor Module D for Processor III;

Figure 7 is a schematic drawing of Processor Module E for Processor IV;

Figure 8 is a schematic drawing of Processor Module F for Processor IV;

In order to carry out the inspection task, products first have to be located. Advantageously inspection can be carried out in two stages: (1) product location and (2) product scrutiny. Product location may conveniently be carried out using the generalised Hough transform. This may be performed directly on grey-scale images, for objects whose shapes are determined only from a look-up table. In order to perform the Hough transform, edge location must be carried out. Processor I has been designed for this purpose, and is therefore able to deliver data from which special reference points in an image containing product may be found. It is crucial to IMP that starting reference points should be located because of the general nature of the Hough transform. It has been found that special reference points can normally be located in an image containing product, and hence this constitutes a sufficiently general procedure to form the basic starting point for the process of inspection.

Given that certain reference points have been located in an image, the next stage of inspection is to analyse the image in their vicinity, thereby enabling objects to be scrutinised. Processor II carries out this function, using an autoscanning module which scans systematically over the region of interest. Scanning over a sub-area of the image is profitable for two reasons: (1) it speeds up processing by eliminating irrelevant areas; (2) it enables a variety of matching processes to be carried out, since the reference point will be of one or other standard type: this means that comparison can be made with previously compiled data sets. The remainder of Processor II contains modules which aid methods by which matching may be achieved. Processor II contains an internal bus which carries information about the position (x,y) of the current pixel relative to that of the reference point. In particular this internal bus carries information on the (r,θ) co-ordinates of the current pixel relative to the reference point, which it has obtained from a downloadable look-up table held in RAM. Only one reference point may be used at any one time, but the look-up table may contain several sets of additional information, each set being relevant to a particular type of object or feature. For example, the additional information may include data on the ideal size of a particular type of object, or other details. Thus Processor II may scan the image successively looking at several objects of various types, and placing output information on each in its output memory. (The latter arrangement will often be used to save time on the VME bus.)

Use of the internal (x,y)/(r,θ)/information bus (which has been designated as the 'Relative Location' or RL-bus) feeds data to the various Modules within Processor II. In particular, these can build up valuable radial and angular intensity histograms which provide rapid means of comparing the region near a special reference point with that expected for a ideal object. Normal intensity histograms of various ranges can also be generated, to aid this analysis, and correlations can be performed for the distribution of particular intensity values, relative to standard distributions. The emphasis here is on rapidly scrutinising specific regions of the image in various standard ways, in order to save the host processor from the bulk of the processing. The host processor is still permitted to interrogate part of the image when Processor II leaves any detail unclear.

Processor I carries out a vital edge detection function: in fact it is optimised for the computation of Hough transforms. For this purpose it is insufficient to compute, and threshold edge magnitude - edge orientation also has to be determined locally. Processor I is designed to determine both edge magnitude and edge orientation. In addition Processor I is used in a novel and unique manner, namely thresholding edge magnitude at a high level. The reason for this is (a) to find a significantly reduced number of edge points, thereby speeding up the whole IMP system, and (b) ensuring that the edge points that are located are of increased accuracy relative to an average edge point. This strategy is enhanced by incorporating within Processor I a double threshold on the pixel intensity value, so that points which are not half way up the intensity scale are eliminated, thereby speeding up processing further.

Processor I has a more complex autoscan unit than Processor II, since it employs a 3 x 3 pixel window instead of a 1 x 1 window. It achieves addional speed-up by (a) saving input pixel data from the previous two pixels (i.e. it only takes in a new 1 x 3 sub-window for every new pixel), (b) pipelining its computation, and (c) saving its output data in its own local high-speed memory, where it is still accessable by the host processor.

The priority levels on the VME bus, starting with the highest, are: level 3: executive (host) processor, which acts as system controller level 2 hardwired and micro-coded co-processors, including Processor I and Processor II level 1 : software co-processors, including DEC T-11 processors level 0: video display circuitry

Software co-processors are more likely to be intelligent than hardware co-processors, since it is easier to build more complex functionality into software than into hardware. Thus hardware co-processors may not be interruptable and should if necessary be permitted to complete their assigned operations. Therefore they are assigned priority level 2 rather than level 1. Video display circuitry has the lowest priority, and is thus able to display images from VME bus memory only when no other activity is occurring on the bus.

Bus grants to processors at the same level of priority are daisy-chained, and those closest to the arbitrator module have highest resulting priority. During algorithm development, or in an industrial system when speed of processing is not at a premium, high level language notation of pixels is useful. The PPL2 notation for pixels within a 5 x 5 window is:

P15 P14 P13 P12 P11

P16 P4 P3 P2 P10

P17 P5 P0 P1 P9

P18 P6 P7 P8 P24

P19 P20 P21 P22 P23 In order to employ this notation for pixels around the location (X,Y) in an image, it is necessary to perform a re-mapping operation. If this is carried out purely in software it will slow access to a miserable level. In the IMP frame store re-mapplng is carried out automatically in a look-up table: IMP actually copes with windows of size up to 7 x 7 by this method, rather than 5 x 5 as in the above example. Clearly, the look-up operation will reduce speed slightly. However, for the two instances cited above, the minimal reduction in speed resulting from direct RAM look-up will be immaterial, and the gains in ease of programming will be very worthwhile. In fact the automatic re-mapping procedure adopted here has the advantage of using absolute rather than Indexed addressing, which itself leads to a speed-up in- pixel access: this is not seen in currently available commercial systems where (say) a 68000 has direct access to all the image data in a huge block of contiguous memory.

The size of look-up table required for re-mapping is that required to combine X with 6 bits of window placement information, and similarly for Y. For a 128 x 128 frame store this means two look-up tables each having 7 + 5 = 13 address bits and 7 co-ordinate data bits plus 1 over-range data bit: and for a 256 x 256 frame store it means two tables have 8 + 6 = 14 address bits and 8 + 1 data bits. For a 128 x 128 frame store two 8K x 8 EPROMs are sufficient for the purpose. Advantageously, apparatus in accordance with the invention may be used for processing signals from an edge detector. This enhances speed of processing by rapid selection of pixels which provide accurate orientation and location information and ignoring other pixels. The principle that is used for selecting pixels giving high location and orientation accuracy is to look for those pixels where the intensity gradient is very uniform. This may be achieved by thresholding an intensity gradient uniformity parameter at high level or a non-uniformity parameter at low level. This may be achieved by taking two symmetrically-weighted sums of pixels near a pixel location under consideration. Advantageously, these may be re-weighted so that they will be exactly equal if the locality has an intensity gradient which is exactly uniform. The difference of the sums provides a convenient non-uniformity parameter which may be detected by a threshold detector set to a convenient value.

The method will be illustrated for a 3 x 3 neighbourhood, where the Sobel operator is being used to detect edges. Using the following notation to describe the pixel intensities in the neighbourhood

we estimate the (Sobel) x and y components of Intensity gradient as

g_x = (C + 2F + I) - (A + 2D + G) g_y = (A + 2B + C) - (C + 2H + I)

and intensity gradient can then be estimated as

g = [g_x ² + g_y ²]^½

or by a suitable approximation. Edge orientation may be deduced from the relative values of g and g using the arctangent function. Symmetric sums of pixel values that may be used for computing gradient uniformity are

s₁ = A + C + G + I s₂ = B + D + F + H s₃ = 4E

Thus possible non-uniformity parameters would be

u₁ = s₂ = s₃ u₂ = s₃ - s₁

u₁ = s₁ - s₂

It will be clear to one skilled In the art that the effect of the uniformity detector is to remove from consideration by a later object locator a good proportion of those edge points where noise is significant or the edge orientation measurement would be otherwise innacurate and at the same timespeed up the algorithm. It will, furthermore, operate in any size of neighbourhood, not just the 3 x 3 one illustrated by the Sobell edge detector. It is not restricted to use with a Sobell edge detector - others such as a Prewett 3 x 3 edge detector may be employed. Other sets of symmetric combinations of sums of weights should be employed and any linear or non-linear combination of these could be used to detect non-uniformity. (E.g. in the 3 x 3 case one could well use u₁ + u₂ + u₃.) In larger neighbourhoods there are many possible uniformity operators.

One function of the uniformity detector is the elimination of noisy locations. Another is the exclusion from consideration of points which are not in their expected position due, for example, to malformation of an object which is being inspected. The uniformity detector would also be able to improve edge orientation accuracy by eliminating cases when a 'step' edge didn't pass closely enough through the centre of a neighbourhood. It here is any offset, accuracy deteriorates but the uniformity operator improves the probability of detecting this.

The uniformity detector may be used to eliminate edge (or apparent edges) locations which are subject to noise. This noise can arise within any of the pixels in the neighbourhood: e.g. with a Sobel detector, noise in any one of the pixesl In the neighbourhood (except the central one!) would reduce the edge orientation accuracy, and the iniformity operator could attempt to detect this. (Of course, it might sometimes fail - e.g. if two pixels were subject to noise and the effect cancelled itself out in the uniformity of the operator but not in the edge orientation operator itself)

It will furthermore be apparent that the screener can act by pre-screening or post-screening or simply in parallel. Parallel screening would be appropriate If special VLSI chips were to be designed, since this would be the fastest operating option. Otherwise pre- or post-screening would be useful for progressively cutting down the data to be handled by a later object detector. Note also that the whole thing could be done in one VLSI chip, rather than having one such chip for edge detection and one for uniformity screening. The important point is that the uniformity detector can be used to speed up the object detection algorithm by reducing the number of points considered.

Other features are that the invention permits use of radial histograms and correlation on the fly. By defining crucial areas in the picture which are relevant for hardware pre-selects for computer removal of redundant information it creates a progressive hierarchy of extraction of data and thus speeds up the inspection process. It does not waste time because it knows where to check any relevant features of image, which are not necessarily only edge points. The computer recalculates edge points on the basis of stored data and of measurements from the scanner. Because it is aware of the background points it does not take them into consideration. The invention finds particular application in industrial inspection of mass produced products such as food items (biscuits, pizzas, cakes and pies and other products of uniform size and shape). It may also be used for the forensic tasks such as number plate recognition and for optical mark and optical character recognition. It is not restricted to optical techniques for image capture and may employ other methods, such as sonar, infra-red or tactile sensing.

16L

Claims

1. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest, comprising detector means for the positional location of individual articles, characterised in that it includes scanning means to capture an image of a region in the vicinity of a located article and analysis means to analyse the significance of features detected by said scanning means, wherein selection means coupled to said positional location means is operable selectively to control the processing of data derived from said scanning means in order preferentially to obtain data relevant to said features of interest.

2. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest as claimed in Claim 1 characterised in that said selection means includes an intensity gradient uniformity detector which serves as an intensity threshold detector.

3. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest as claimed in Claim 2 characterised in that it includes rejection means to reject from further analysis the signals derived from certain of said features.

4. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest as claimed in Claim 3 characterised in that the rejection means is adapted to reject signals which are subject to noise greater than a predetermined level.

5. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest as claimed in Claim 3 characterised in that the rejection means is adapted to reject signals which to not conform to a predetermined profile.

6. Inspection apparatus for the successive inspection of a plurality of articles having a common set of features of interest as claimed in Claim 5 characterised in that the profile is determined by the location of a step edge relative to the centre of a population of measured Intensities.

7. An image location device for use in inspection apparatus in accordance with any one of the preceding claims characterised in that it comprises detecor means for deriving a plurality of electric signals corresponding to the intensity of the optical signal at a plurality of positions in the vicinity of a predetermined position on an optical image, combining means for combining pairs of symmetrically-weighted groups of said electrical signals in accordance with a predetermined algorithm to derive a pair of electrical signals dependent on the intensity of the optical signals at positions in the vicinity of said predetermined position and difference means to derive an electrical signal dependent on the difference between said pair of electrical signals.