/*-------------------------------------------------------------*/ /* An NCL program for feature detection in a pixel array */ /* (C) 1993 Zdravko Markov, II-BAS */ /*-------------------------------------------------------------*/ /* DESCRIPTION: ----------- This program processes a binary image, represented as a pixel array. Three types of features are looked for - vertical, horizontal and diagonal subdomains. These objects are represented as relations between neighboring pixels or domains of pixels grouped in squares 2 by 2. The program represents an 8-layer network of partly overlapping squares - an input image 8X8 pixels (64 free nodes), layer 1 built out of 7X7 spreading activation nodes, layer 2 - 6X6 nodes, ..., and layer 7 - an output node. The basic processing unit in the network is a spreading activation node activated when at least two of the pixels (sub-domains) of the square are "on" (the corresponding net-variables are bound), i.e. its threshold is 2. The output of the node is determined by a Prolog procedure, defining the properties of the objects in terms of spatial relations between the neighboring pixels or domains of pixels. If neither of the defined objects is recognized then the node produces as output the compound term pat(A,B,C,D), where A,B,C,D are the terms found in each of the object sub-squares. This term is further propagated to the nodes of the next layers of the network, where it can be possibly recognized. REFERENCE: --------- Markov, Z., A Tool for Building Connectionist-like Networks Based on Term Unification, in: M. Richter and H. Boley (eds.), Proceedings of PDK'91, LNCS (LNAI), Vol. 567, Springer-Verlag, 1991, 119-203. */ /*----------------------- Layer 1 -----------------------------*/ a(11,A11):a(21,A21):a(31,A31):a(41,A41): a(51,A51):a(61,A61):a(71,A71):a(81,A81): a(12,A12):a(22,A22):a(32,A32):a(42,A42): a(52,A52):a(62,A62):a(72,A72):a(82,A82): a(13,A13):a(23,A23):a(33,A33):a(43,A43): a(53,A53):a(63,A63):a(73,A73):a(83,A83): a(14,A14):a(24,A24):a(34,A34):a(44,A44): a(54,A54):a(64,A64):a(74,A74):a(84,A84): a(15,A15):a(25,A25):a(35,A35):a(45,A45): a(55,A55):a(65,A65):a(75,A75):a(85,A85): a(16,A16):a(26,A26):a(36,A36):a(46,A46): a(56,A56):a(66,A66):a(76,A76):a(86,A86): a(17,A17):a(27,A27):a(37,A37):a(47,A47): a(57,A57):a(67,A67):a(77,A77):a(87,A87): a(18,A18):a(28,A28):a(38,A38):a(48,A48): a(58,A58):a(68,A68):a(78,A78):a(88,A88): node(A11,A21,A12,A22,2,p(A11,A21,A12,A22,B11)): node(A21,A31,A22,A32,2,p(A21,A31,A22,A32,B21)): node(A31,A41,A32,A42,2,p(A31,A41,A32,A42,B31)): node(A41,A51,A42,A52,2,p(A41,A51,A42,A52,B41)): node(A51,A61,A52,A62,2,p(A51,A61,A52,A62,B51)): node(A61,A71,A62,A72,2,p(A61,A71,A62,A72,B61)): node(A71,A81,A72,A82,2,p(A71,A81,A72,A82,B71)): node(A12,A22,A13,A23,2,p(A12,A22,A13,A23,B12)): node(A22,A32,A23,A33,2,p(A22,A32,A23,A33,B22)): node(A32,A42,A33,A43,2,p(A32,A42,A33,A43,B32)): node(A42,A52,A43,A53,2,p(A42,A52,A43,A53,B42)): node(A52,A62,A53,A63,2,p(A52,A62,A53,A63,B52)): node(A62,A72,A63,A73,2,p(A62,A72,A63,A73,B62)): node(A72,A82,A73,A83,2,p(A72,A82,A73,A83,B72)): node(A13,A23,A14,A24,2,p(A13,A23,A14,A24,B13)): node(A23,A33,A24,A34,2,p(A23,A33,A24,A34,B23)): node(A33,A43,A34,A44,2,p(A33,A43,A34,A44,B33)): node(A43,A53,A44,A54,2,p(A43,A53,A44,A54,B43)): node(A53,A63,A54,A64,2,p(A53,A63,A54,A64,B53)): node(A63,A73,A64,A74,2,p(A63,A73,A64,A74,B63)): node(A73,A83,A74,A84,2,p(A73,A83,A74,A84,B73)): node(A14,A24,A15,A25,2,p(A14,A24,A15,A25,B14)): node(A24,A34,A25,A35,2,p(A24,A34,A25,A35,B24)): node(A34,A44,A35,A45,2,p(A34,A44,A35,A45,B34)): node(A44,A54,A45,A55,2,p(A44,A54,A45,A55,B44)): node(A54,A64,A55,A65,2,p(A54,A64,A55,A65,B54)): node(A64,A74,A65,A75,2,p(A64,A74,A65,A75,B64)): node(A74,A84,A75,A85,2,p(A74,A84,A75,A85,B74)): node(A15,A25,A16,A26,2,p(A15,A25,A16,A26,B15)): node(A25,A35,A26,A36,2,p(A25,A35,A26,A36,B25)): node(A35,A45,A36,A46,2,p(A35,A45,A36,A46,B35)): node(A45,A55,A46,A56,2,p(A45,A55,A46,A56,B45)): node(A55,A65,A56,A66,2,p(A55,A65,A56,A66,B55)): node(A65,A75,A66,A76,2,p(A65,A75,A66,A76,B65)): node(A75,A85,A76,A86,2,p(A75,A85,A76,A86,B75)): node(A16,A26,A17,A27,2,p(A16,A26,A17,A27,B16)): node(A26,A36,A27,A37,2,p(A26,A36,A27,A37,B26)): node(A36,A46,A37,A47,2,p(A36,A46,A37,A47,B36)): node(A46,A56,A47,A57,2,p(A46,A56,A47,A57,B46)): node(A56,A66,A57,A67,2,p(A56,A66,A57,A67,B56)): node(A66,A76,A67,A77,2,p(A66,A76,A67,A77,B66)): node(A76,A86,A77,A87,2,p(A76,A86,A77,A87,B76)): node(A17,A27,A18,A28,2,p(A17,A27,A18,A28,B17)): node(A27,A37,A28,A38,2,p(A27,A37,A28,A38,B27)): node(A37,A47,A38,A48,2,p(A37,A47,A38,A48,B37)): node(A47,A57,A48,A58,2,p(A47,A57,A48,A58,B47)): node(A57,A67,A58,A68,2,p(A57,A67,A58,A68,B57)): node(A67,A77,A68,A78,2,p(A67,A77,A68,A78,B67)): node(A77,A87,A78,A88,2,p(A77,A87,A78,A88,B77)): /*----------------------- Layer 2 -----------------------------*/ node(B11,B21,B12,B22,2,p(B11,B21,B12,B22,C11)): node(B21,B31,B22,B32,2,p(B21,B31,B22,B32,C21)): node(B31,B41,B32,B42,2,p(B31,B41,B32,B42,C31)): node(B41,B51,B42,B52,2,p(B41,B51,B42,B52,C41)): node(B51,B61,B52,B62,2,p(B51,B61,B52,B62,C51)): node(B61,B71,B62,B72,2,p(B61,B71,B62,B72,C61)): node(B12,B22,B13,B23,2,p(B12,B22,B13,B23,C12)): node(B22,B32,B23,B33,2,p(B22,B32,B23,B33,C22)): node(B32,B42,B33,B43,2,p(B32,B42,B33,B43,C32)): node(B42,B52,B43,B53,2,p(B42,B52,B43,B53,C42)): node(B52,B62,B53,B63,2,p(B52,B62,B53,B63,C52)): node(B62,B72,B63,B73,2,p(B62,B72,B63,B73,C62)): node(B13,B23,B14,B24,2,p(B13,B23,B14,B24,C13)): node(B23,B33,B24,B34,2,p(B23,B33,B24,B34,C23)): node(B33,B43,B34,B44,2,p(B33,B43,B34,B44,C33)): node(B43,B53,B44,B54,2,p(B43,B53,B44,B54,C43)): node(B53,B63,B54,B64,2,p(B53,B63,B54,B64,C53)): node(B63,B73,B64,B74,2,p(B63,B73,B64,B74,C63)): node(B14,B24,B15,B25,2,p(B14,B24,B15,B25,C14)): node(B24,B34,B25,B35,2,p(B24,B34,B25,B35,C24)): node(B34,B44,B35,B45,2,p(B34,B44,B35,B45,C34)): node(B44,B54,B45,B55,2,p(B44,B54,B45,B55,C44)): node(B54,B64,B55,B65,2,p(B54,B64,B55,B65,C54)): node(B64,B74,B65,B75,2,p(B64,B74,B65,B75,C64)): node(B15,B25,B16,B26,2,p(B15,B25,B16,B26,C15)): node(B25,B35,B26,B36,2,p(B25,B35,B26,B36,C25)): node(B35,B45,B36,B46,2,p(B35,B45,B36,B46,C35)): node(B45,B55,B46,B56,2,p(B45,B55,B46,B56,C45)): node(B55,B65,B56,B66,2,p(B55,B65,B56,B66,C55)): node(B65,B75,B66,B76,2,p(B65,B75,B66,B76,C65)): node(B16,B26,B17,B27,2,p(B16,B26,B17,B27,C16)): node(B26,B36,B27,B37,2,p(B26,B36,B27,B37,C26)): node(B36,B46,B37,B47,2,p(B36,B46,B37,B47,C36)): node(B46,B56,B47,B57,2,p(B46,B56,B47,B57,C46)): node(B56,B66,B57,B67,2,p(B56,B66,B57,B67,C56)): node(B66,B76,B67,B77,2,p(B66,B76,B67,B77,C66)): /*------------------------- Layer 3 ---------------------------*/ node(C11,C21,C12,C22,2,p(C11,C21,C12,C22,D11)): node(C21,C31,C22,C32,2,p(C21,C31,C22,C32,D21)): node(C31,C41,C32,C42,2,p(C31,C41,C32,C42,D31)): node(C41,C51,C42,C52,2,p(C41,C51,C42,C52,D41)): node(C51,C61,C52,C62,2,p(C51,C61,C52,C62,D51)): node(C12,C22,C13,C23,2,p(C12,C22,C13,C23,D12)): node(C22,C32,C23,C33,2,p(C22,C32,C23,C33,D22)): node(C32,C42,C33,C43,2,p(C32,C42,C33,C43,D32)): node(C42,C52,C43,C53,2,p(C42,C52,C43,C53,D42)): node(C52,C62,C53,C63,2,p(C52,C62,C53,C63,D52)): node(C13,C23,C14,C24,2,p(C13,C23,C14,C24,D13)): node(C23,C33,C24,C34,2,p(C23,C33,C24,C34,D23)): node(C33,C43,C34,C44,2,p(C33,C43,C34,C44,D33)): node(C43,C53,C44,C54,2,p(C43,C53,C44,C54,D43)): node(C53,C63,C54,C64,2,p(C53,C63,C54,C64,D53)): node(C14,C24,C15,C25,2,p(C14,C24,C15,C25,D14)): node(C24,C34,C25,C35,2,p(C24,C34,C25,C35,D24)): node(C34,C44,C35,C45,2,p(C34,C44,C35,C45,D34)): node(C44,C54,C45,C55,2,p(C44,C54,C45,C55,D44)): node(C54,C64,C55,C65,2,p(C54,C64,C55,C65,D54)): node(C15,C25,C16,C26,2,p(C15,C25,C16,C26,D15)): node(C25,C35,C26,C36,2,p(C25,C35,C26,C36,D25)): node(C35,C45,C36,C46,2,p(C35,C45,C36,C46,D35)): node(C45,C55,C46,C56,2,p(C45,C55,C46,C56,D45)): node(C55,C65,C56,C66,2,p(C55,C65,C56,C66,D55)): /*------------------------- Layer 4 ---------------------------*/ node(D11,D21,D12,D22,2,p(D11,D21,D12,D22,E11)): node(D21,D31,D22,D32,2,p(D21,D31,D22,D32,E21)): node(D31,D41,D32,D42,2,p(D31,D41,D32,D42,E31)): node(D41,D51,D42,D52,2,p(D41,D51,D42,D52,E41)): node(D12,D22,D13,D23,2,p(D12,D22,D13,D23,E12)): node(D22,D32,D23,D33,2,p(D22,D32,D23,D33,E22)): node(D32,D42,D33,D43,2,p(D32,D42,D33,D43,E32)): node(D42,D52,D43,D53,2,p(D42,D52,D43,D53,E42)): node(D13,D23,D14,D24,2,p(D13,D23,D14,D24,E13)): node(D23,D33,D24,D34,2,p(D23,D33,D24,D34,E23)): node(D33,D43,D34,D44,2,p(D33,D43,D34,D44,E33)): node(D43,D53,D44,D54,2,p(D43,D53,D44,D54,E43)): node(D14,D24,D15,D25,2,p(D14,D24,D15,D25,E14)): node(D24,D34,D25,D35,2,p(D24,D34,D25,D35,E24)): node(D34,D44,D35,D45,2,p(D34,D44,D35,D45,E34)): node(D44,D54,D45,D55,2,p(D44,D54,D45,D55,E44)): /*------------------------ Layer 5 ----------------------------*/ node(E11,E21,E12,E22,2,p(E11,E21,E12,E22,F11)): node(E21,E31,E22,E32,2,p(E21,E31,E22,E32,F21)): node(E31,E41,E32,E42,2,p(E31,E41,E32,E42,F31)): node(E12,E22,E13,E23,2,p(E12,E22,E13,E23,F12)): node(E22,E32,E23,E33,2,p(E22,E32,E23,E33,F22)): node(E32,E42,E33,E43,2,p(E32,E42,E33,E43,F32)): node(E13,E23,E14,E24,2,p(E13,E23,E14,E24,F13)): node(E23,E33,E24,E34,2,p(E23,E33,E24,E34,F23)): node(E33,E43,E34,E44,2,p(E33,E43,E34,E44,F33)): /*------------------------ Layer 6 ----------------------------*/ node(F11,F21,F12,F22,2,p(F11,F21,F12,F22,G11)): node(F21,F31,F22,F32,2,p(F21,F31,F22,F32,G21)): node(F12,F22,F13,F23,2,p(F12,F22,F13,F23,G12)): node(F22,F32,F23,F33,2,p(F22,F32,F23,F33,G22)): /*------------------------ Layer 7 ----------------------------*/ node(G11,G21,G12,G22,2,p(G11,G21,G12,G22,Out)): out(Out). /*---------------------- Node Procedure -----------------------*/ p(X,Y,_,_,h):-nonvar(X),nonvar(Y),X=Y,!. p(X,_,Y,_,v):-nonvar(X),nonvar(Y),X=Y,!. p(X,_,_,Y,d2):-nonvar(X),nonvar(Y),X=Y,!. p(_,X,Y,_,d1):-nonvar(X),nonvar(Y),X=Y,!. p(_,X,_,Y,v):-nonvar(X),nonvar(Y),X=Y,!. p(_,_,X,Y,h):-nonvar(X),nonvar(Y),X=Y,!. p(A,B,C,D,pat(A,B,C,D)). /*------------------ Auxiliary Procedures ---------------------*/ /* Seting up the inputs */ on([]):-!. on([X|T]):-a(X,on),on(T). /*-------------------------------------------------------------*/ /* Interactive input of images - for the PC version only !!! */ /*-------------------------------------------------------------*/ pix(O):-delete(cp),delete(ref),delete(example), clear,cursor(X,Y),assertz(ref(X,Y)), repeat,inkey(Key),go(Key), setof(Z,(cp(A,B),Z is ((A+1)/2)*10+B),L),!, nl,write(L),nl, top(T),on(L),spread(T),out(O). go(13):-cursor(X,Y),( retract(cp(X,Y)),write(' '); assertz(cp(X,Y)),put(219),put(219) ),goxy(X,Y),!,fail. go(~22):-ref(_,Y0),cursor(X,Y),YY0,Y1 is Y-1,goxy(X,Y1),!,fail. go(~19):-ref(X0,_),cursor(X,Y),XX0,X1 is X-2,goxy(X1,Y),!,fail. go(27):-!. /*-------------------------------------------------------------*/ /* EXAMPLES: */ /*-------------------------------------------------------------*/ ?- netmode(0). /* Breadth-first mode only ! */ /* šššššššššššššššš ?- top(T),on([13,23,33,43,53,63,73,83]),spread(T),out(X). X=h ?- top(T),on([41,42,43,44,45,46,47,48]),spread(T),out(X). X=v ?- top(T),on([11,22,33,44,55,66,77,88]),spread(T),out(X). X=d2 ?- top(T),on([11,12,21,22,33,34,44,43,55,56,66,65,77,78,88,87]), spread(T),out(X). X=d2 ?- top(T),on([13,23,33,43,53,63,73,83,14,24,34,44,54,64,74,84]), spread(T),out(X). X=h ?- top(T),on([41,42,43,44,45,55,56,47,48]), spread(T),out(X). X=v ?- top(T),on([11,21,31,41,51,61,71,81,52,53,54,55,56,57,58]), spread(T),out(X). X=h */