A three-layered neural network to perform the well-known Huffman-Clowes scene labeling that is a typical constraint satisfaction problem in artificial intelligence is proposed. The proposed constraint propagation neural network uses the topology and the interconnections of neurons to achieve global consistency through propagating local constraints. Given a line drawing, the proposed neural network establishes a consistent labeling for all the edges or detects an inconsistency. The structure of this neural network consists of three layers: the edge, the vertex, and the junction type layers. The first layer of this network contains the initial or final decisions about the junction labels associated with the vertices. Since each edge is shared by two junctions, it is represented by two vectors (one for each junction) and connects with the vertex of the junction represented by a neuron in the second layer. Once one of these two edge vectors is labeled, the information is propagated to the other edge vector representing the same edge in the input line drawing. In the second layer, each neuron represents a vertex in the input line drawing and sums up the weighted signals from the first layer. Then, there is a competition among the neurons and only one neuron is selected (based on the magnitude of its incoming signals) as the winner to fire. This winner becomes the candidate to be labeled next. The output of the winner is not only forwarded to the third layer for deciding which valid junction type it belongs to but also fed back to the first layer for updating its edges. The neurons in the third layer receive the signals sent by the winner in the second layer and the information about the edges associated with this winner. There are 18 neurons in the third layer representing the 18 junction types. The connections between this layer and the first layer encode the labels of the edges of the junction types. Once the junction type is determined, the representing neuron (in the third layer) sends the information about its labels to the edges (in the first layer) associated with the winner in the second layer. This process iterates until a consistent labeling is found or an inconsistency is detected. Experimental results show that this approach exploits the parallel architecture inherent in the network and is faster than the conventional algorithmic method.
ASJC Scopus subject areas