On Image Matching and Feature Tracking for Embedded Systems: A State-of-the-Art - Advances in Heuristic Signal Processing and Applications - page 360

Fig. 16.6 The internal architecture of the μ DP circuit and its operation during matching ( left :path
parallel development)
to O(N) . Each PE has necessary calculation and memory resources for calculating
values of the form d ij . Moreover, each PE remembers the PE which activated it.
This information is useful for backtracking in order to find the optimal match. RE-
CEPTION and ACTIVATION are two signals implemented in each PE for a data
asynchronous exchange protocol. The whole matching algorithm is executed in 2 N
steps in the worst case.
The code below gives the main steps of the matching algorithm. The TIMER
variable records the temporal length (equivalent to the matching cost) of the best
global path found so far.
/* local cost calculation in forward direction */
PE(0,0)=ACTIVE; / μ PD calculation starts by external activation of PE(0,0) */
FIN=FALSE;
Score_temp := 0 ;
WHILE (NOT FIN) DO IN PARALLEL on ALL Active PEs
IF RECEPTION(Score_temp) from neighbor THAN
TIMER := score_temp;
MEMORIZE the direction s of activation;
UP DATE TIMER_temp in 3 directions;
WAIT until TIMER=dij.C(diagonal) THAN
ACTIVATE & FORWARD TIMER_temp to diagonal neighbor;
WAIT until TIMER=dij.C(orthogonal) THAN
ACTIVATE & FORWARD TIMER_temp to orthogonal neighbors;
FIN=IF(no_more PE) THAN TRUE;
DEACTIVATE yourself;
END IF;
END WHILE
SCORE= TIMER (N,N);
/* Backtracking of the optimal path; POSITION gives the PE ij through which optimal path passes */
i=2*N;
PATH(i)= (POSITION=(N,N));
WHILE (NOT PATH(i)=(0,0)) DO
POSITION=POSITION-s(POSITION);
i=i-1;
PATH(i)=POSITION;
END WHILE /* PATH = optimal path */