Routing techniques using serial neighborhood image analyzing system

Claim 3

The method of claim 1 wherein the neighborhood transformation logic means in step (b) performs the following sequence of operation: (test 1) determining whether the center pixel in each neighborhood has a value associated with a free or target pixel; and (test 2) determining whether the neighbor pixels of the center pixel have values associated with source or arrow pixels; if tests 1 and 2 are met, the neighborhood transformation logic means operating to generate a transformation output with a value associated with an arrow pointing to the source for that neighborhood and, otherwise, the unchanged value of the center pixel as the transformation output.

Claim 4

The method of claim 2 wherein said neighborhood transformation logic means includes adder means for adding together values applied to its inputs, means for sequentially connecting the pixels in each neighborhood to one input of the adder, and means for applying a programmable contribution value to the other input of the adder; and wherein step (b) is performed by generating various contribution values, detecting the output of the adder, and generating the transformation output for the stage as a function of the detected output of the adder.

Claim 5

The method of claim 3 wherein each pixel is represented by a plurality of bits, the free pixels and target pixels having binary values in which the least significant bit has a logical zero state; and wherein (test 1) is performed by masking at least some of the more significant bits, generating a contribution value of zero and determining whether the output of the adder means is zero when the center pixel is applied to the one input of the adder.

Claim 6

The method of claim 4 wherein said source and arrow pixels have binary values greater than or equal to 2; and Wherein (test 2) is performed by generating a contribution value of -2 and detecting whether the adder generates a carry out bit when the neighbor pixels are applied to the other adder input.

Claim 7

The method of claim 1 wherein said neighborhood transformation logic means performs step (b) by testing each neighborhood in the image and generating a transformation output for the stage as follows: TABLE I ______________________________________ Λ = { ←,↑,↓,→,S} ______________________________________ GROW OUT: 1. IF center ε{O,T} THEN BEGIN 2. IF n εΛ THEN attach ↑ to center 3. ELSE IF w εΛ THEN attach ← to center 4. ELSE IF eεΛ THEN attach → to center 5. ELSE IF sεΛ THEN attach ↓ to center ______________________________________ where the arrows, S, O, T are preselected pixel values associated with arrow pixels, source pixels, free pixels, and target pixels, respectively; and wherein n, w, e, and s are north, west, east and south neighbor pixels in the extracted neighborhood.

Claim 8

The method of claim 1 where in step (b) the target pixel is transformed to a given value including an arrow pixel value pointing back towards the source and wherein step (c) is carried out by the neighborhood transformation logic means of the stage by performing the following tests: (test 3) determining whether the center pixel in each neighborhood has a vaue associated with an arrow or the source; and (test 4) determining whether any of the neighbor pixels have said given value associated with the target and an arrow pointing towards said center pixel; if tests 3 and 4 are met, the transformation logic means operating to transform the value of the center pixel to a value asociated with the conductor path between the target and source; and otherwise, using the unchanged value of the center pixel as the transformation output for the stage.

Claim 9

The method of claim 7 wherein the conductor path pixel values provided in step (c) all include the same binary logic state in a given bit position; and wherein step (d) changes the values of all pixels whose given bit position contains said state into a value associated with blocked areas of the circuit.

Claim 10

The method of claim 6 wherein the neighborhood transformation logic means in step (c) analyzes each neighborhood and generates a transformation output therefore as follows: TABLE II ______________________________________ TRACE-BACK: IF center εΛ AND ((n = T↓)OR(w = T→)OR(e = T←)OR(s = T↑)) THEN attach T to center ______________________________________ where T--arrow is a pixel having a value associated with a portion of the conductor path beginning from the target.