lgra.txt

动态场景中运动目标检测提取与跟踪 对新手很有用

	}
	else
	{
		/* no parent is found */
		i -> TS = 0;
		i -> is_sink = 1;

		/* process neighbors */
		for (a0=i->first; a0; a0=a0->next)
		{
			j = a0 -> head;
			if (!j->is_sink && (a=j->parent))
			{
				if (a0->sister->r_cap) set_active(j);
				if (a!=TERMINAL && a!=ORPHAN && a->head==i)
				{
					/* add j to the adoption list */
					j -> parent = ORPHAN;
					np = nodeptr_block -> New();
					np -> ptr = j;
					if (orphan_last) orphan_last -> next = np;
					else             orphan_first        = np;
					orphan_last = np;
					np -> next = NULL;
				}
			}
		}
	}
}

void Graph::process_sink_orphan(node *i)
{
	node *j;
	arc *a0, *a0_min = NULL, *a;
	nodeptr *np;
	int d, d_min = INFINITE_D;

	if (i->parent!=ORPHAN) return;

	/* trying to find a new parent */

	for (a0=i->first; a0; a0=a0->next)
	if (a0->r_cap!=0)
	{
		j = a0 -> head;
		if (j->is_sink && (a=j->parent))
		{
			/* checking the origin of j */
			d = 0;
			while ( 1 )
			{
				if (j->TS == TIME)
				{
					d += j -> DIST;
					break;
				}
				a = j -> parent;
				d ++;
				if (a==TERMINAL)
				{
					j -> TS = TIME;
					j -> DIST = 1;
					break;
				}
				if (a==ORPHAN) { d = INFINITE_D; break; }
				j = a -> head;
			}
			if (d<INFINITE_D) /* j originates from the sink - done */
			{
				if (d<d_min)
				{
					a0_min = a0;
					d_min = d;
				}
				/* set marks along the path */
				for (j=a0->head; j->TS!=TIME; j=j->parent->head)
				{
					j -> TS = TIME;
					j -> DIST = d --;
				}
			}
		}
	}

	if (i->parent = a0_min)
	{
		i -> TS = TIME;
		i -> DIST = d_min + 1;
	}
	else
	{
		/* no parent is found */
		i -> TS = 0;
		i -> is_sink = 0;

		/* process neighbors */
		for (a0=i->first; a0; a0=a0->next)
		{
			j = a0 -> head;
			if (j->is_sink && (a=j->parent))
			{
				if (a0->r_cap) set_active(j);
				if (a!=TERMINAL && a!=ORPHAN && a->head==i)
				{
					/* add j to the adoption list */
					j -> parent = ORPHAN;
					np = nodeptr_block -> New();
					np -> ptr = j;
					if (orphan_last) orphan_last -> next = np;
					else             orphan_first        = np;
					orphan_last = np;
					np -> next = NULL;
				}
			}
		}
	}
}

/***********************************************************************/

Graph::flowtype Graph::maxflow()
{
	int aug_num=0;
	node *i, *j, *current_node = NULL;
	arc *a;
	nodeptr *np, *np_next;

	maxflow_init();

nodeptr_block = new DBlock<nodeptr>(NODEPTR_BLOCK_SIZE, error_function);

while ( 1 )
{
	if (i=current_node)
	{
		i -> next = NULL; /* remove active flag */
		if (!i->parent) i = NULL;
	}
	if (!i)
	{
		if (!(i = next_active())) break;
	}


	/* growth */
	if (!i->is_sink)
	{
		/* grow source tree */
		for (a=i->first; a; a=a->next)
		if (a->r_cap)
		{
			j = a -> head;
			if (!j->parent)
			{
				j -> is_sink = 0;
				j -> parent = a -> sister;
				j -> TS = i -> TS;
				j -> DIST = i -> DIST + 1;
				set_active(j);
			}
			else if (j->is_sink) break;
			else if (j->TS <= i->TS && j->DIST > i->DIST)
			{
				/* heuristic - trying to make the distance from j to the source shorter */
				j -> parent = a -> sister;
				j -> TS = i -> TS;
				j -> DIST = i -> DIST + 1;
			}
		}
	}
	else
	{
		/* grow sink tree */
		for (a=i->first; a; a=a->next)
		if (a->sister->r_cap)
		{
			j = a -> head;
			if (!j->parent)
			{
				j -> is_sink = 1;
				j -> parent = a -> sister;
				j -> TS = i -> TS;
				j -> DIST = i -> DIST + 1;
				set_active(j);
			}
			else if (!j->is_sink) { a = a -> sister; break; }
			else if (j->TS <= i->TS && j->DIST > i->DIST)
			{
				/* heuristic - trying to make the distance from j to the sink shorter */
				j -> parent = a -> sister;
				j -> TS = i -> TS;
				j -> DIST = i -> DIST + 1;
			}
		}
	}

	TIME ++;

	if (a)
	{
		i -> next = i; /* set active flag */
		current_node = i;

		/* augmentation */

		aug_num++;
		augment(a);

		/* augmentation end */

		/* adoption */
		while (np=orphan_first)
		{
			np_next = np -> next;
			np -> next = NULL;

			while (np=orphan_first)
			{
				orphan_first = np -> next;
				i = np -> ptr;
				nodeptr_block -> Delete(np);
				if (!orphan_first) orphan_last = NULL;
				if (i->is_sink) process_sink_orphan(i);
				else process_source_orphan(i);
			}

			orphan_first = np_next;
		}
		/* adoption end */
	}
	else current_node = NULL;
}

queue_first[0] = NULL;
queue_first[1] = NULL;
queue_last[0] = NULL;
queue_last[1] = NULL;

TIME++;	

//printf("%d Augmentation paths found\n",aug_num);
return flow;
}

/***********************************************************************/


Graph::flowtype Graph::revised_maxflow()
{
	int aug_num=0;
	node *i, *j, *current_node = NULL;
	arc *a;
	nodeptr *np, *np_next;

	/* adoption */	


	while (np=orphan_first)
	{
		np_next = np -> next;
		np -> next = NULL;

		while (np=orphan_first)
		{
			orphan_first = np -> next;
			i = np -> ptr;
			nodeptr_block -> Delete(np);
			if (!orphan_first) orphan_last = NULL;
			if (i->is_sink) process_sink_orphan(i);
			else process_source_orphan(i);
		}

		orphan_first = np_next;
	}

	/* adoption end */

	while ( 1 )
	{
		if (i=current_node)
		{
			i -> next = NULL; /* remove active flag */
			if (!i->parent) i = NULL;
		}
		
		if (!i)
		{
			
			i = next_active();

			if (!i) break;		

			while ((i->parent==NULL)||(i->parent==ORPHAN))
			{
				i = next_active();	
				if (!i) break;		
			}
				
		}
		
		/* growth */
		if (!i->is_sink)
		{
			/* grow source tree */
			for (a=i->first; a; a=a->next)
			if (a->r_cap)
			{
				j = a -> head;
				if (j->parent==NULL)
				{
					j -> is_sink = 0;
					j -> parent = a -> sister;
					j -> TS = i -> TS;
					j -> DIST = i -> DIST + 1;
					set_active(j);
				}
				else if (j->is_sink) break;
				else if (j->TS <= i->TS && j->DIST > i->DIST)
				{
					/* heuristic - trying to make the distance from j to the source shorter */
					j -> parent = a -> sister;
					j -> TS = i -> TS;
					j -> DIST = i -> DIST + 1;
				}
			}
		}
		else
		{
			/* grow sink tree */
			for (a=i->first; a; a=a->next)
			if (a->sister->r_cap)
			{
				j = a -> head;
				if (j->parent==NULL)
				{
					j -> is_sink = 1;
					j -> parent = a -> sister;
					j -> TS = i -> TS;
					j -> DIST = i -> DIST + 1;
					set_active(j);
				}
				else if (!j->is_sink) { a = a -> sister; break; }
				else if (j->TS <= i->TS && j->DIST > i->DIST)
				{
					/* heuristic - trying to make the distance from j to the sink shorter */
					j -> parent = a -> sister;
					j -> TS = i -> TS;
					j -> DIST = i -> DIST + 1;
				}
			}
		}

		TIME ++;

		if (a)
		{
			i -> next = i; /* set active flag */
			current_node = i;

			/* augmentation */

			aug_num++;
			augment(a);

			/* augmentation end */

			/* adoption */
			while (np=orphan_first)
			{
				np_next = np -> next;
				np -> next = NULL;

				while (np=orphan_first)
				{
					orphan_first = np -> next;
					i = np -> ptr;
					nodeptr_block -> Delete(np);
					if (!orphan_first) orphan_last = NULL;
					if (i->is_sink) process_sink_orphan(i);
					else            process_source_orphan(i);
				}

				orphan_first = np_next;
			}
			/* adoption end */
		}
		else current_node = NULL;
	}
	TIME++;
	//printf("%d Augmentation paths found\n",aug_num);
	return flow;
}


/***********************************************************************/


Graph::termtype Graph::what_segment(node_id i)
{
	if (!((node*)i)->is_sink) return SOURCE;
	return SINK;
}


/***********************************************************************/


void Graph::process_source_orphan_tree(node *i)
{
	node *j;
	arc *a0, *a0_min = NULL, *a;
	nodeptr *np;
	int d, d_min = INFINITE_D;
	int d_issink;

	if (i->parent!=ORPHAN) return;

	/* trying to find a new parent */
	for (a0=i->first; a0; a0=a0->next)
	{
		j = a0 -> head;
		a=j->parent;

		if ((((a0->sister->r_cap)&&(!j->is_sink))||((a0->r_cap)&&(j->is_sink)))&&(a!=NULL)&&(a!=ORPHAN))
		{
			/* checking the origin of j */

			d = 0;
			while ( 1 )
			{
				if (j->TS == TIME)
				{
					d += j -> DIST;
					break;
				}
				a = j -> parent;
				d ++;
				if (a==TERMINAL)
				{
					j -> TS = TIME;
					j -> DIST = 1;
					break;
				}
				if (a==ORPHAN) { d = INFINITE_D; break; }
				j = a -> head;
			}
			if (d<INFINITE_D) 
			{
				if (d<d_min)
				{
					a0_min = a0;
					d_min = d;
					d_issink = j->is_sink;
				}

				for (j=a0->head; j->TS!=TIME; j=j->parent->head)
				{
					j -> TS = TIME;
					j -> DIST = d --;
				}
			}
		}
	}

	if (i->parent = a0_min)
	{
		i -> TS = TIME;
		i -> DIST = d_min + 1;
		i->is_sink = d_issink;
		
		if (d_issink==1)
		{
			/* process neighbors */
			for (a0=i->first; a0; a0=a0->next)
			{
				j = a0 -> head;
				if (!j->is_sink && (a=j->parent))
				{
					if (a0->sister->r_cap) set_active(j);
					if (a!=TERMINAL && a!=ORPHAN && a->head==i)
					{
						/* add j to the adoption list */
						j -> parent = ORPHAN;
						np = nodeptr_block -> New();
						np -> ptr = j;
						if (orphan_last) orphan_last -> next = np;
						else             orphan_first        = np;
						orphan_last = np;
						np -> next = NULL;
					}
				}
			}
		}
	}
	else
	{
		/* no parent is found */
		i -> TS = 0;

		/* process neighbors */
		for (a0=i->first; a0; a0=a0->next)
		{
			j = a0 -> head;
			if (!j->is_sink && (a=j->parent))
			{
				if (a0->sister->r_cap) set_active(j);
				if (a!=TERMINAL && a!=ORPHAN && a->head==i)
				{
					/* add j to the adoption list */
					j -> parent = ORPHAN;
					np = nodeptr_block -> New();
					np -> ptr = j;
					if (orphan_last) orphan_last -> next = np;
					else             orphan_first        = np;
					orphan_last = np;
					np -> next = NULL;
				}
			}
		}
	}
}

/***********************************************************************/


void Graph::process_sink_orphan_tree(node *i)
{
	node *j;
	arc *a0, *a0_min = NULL, *a;
	nodeptr *np;
	int d, d_min = INFINITE_D;
	int d_issink;

	if (i->parent!=ORPHAN) return;

	/* trying to find a new parent */
	for (a0=i->first; a0; a0=a0->next)
	{
		j = a0 -> head;
		a=j->parent;

		if ((((a0->sister->r_cap)&&(!j->is_sink))||((a0->r_cap)&&(j->is_sink)))&&(a!=NULL)&&(a!=ORPHAN))
		{
			/* checking the origin of j */

			d = 0;
			while ( 1 )
			{
				if (j->TS == TIME)
				{
					d += j -> DIST;
					break;
				}
				a = j -> parent;
				d ++;
				if (a==TERMINAL)
				{
					j -> TS = TIME;
					j -> DIST = 1;
					break;
				}
				if (a==ORPHAN) { d = INFINITE_D; break; }
				j = a -> head;
			}
			if (d<INFINITE_D) 
			{
				if (d<d_min)
				{
					a0_min = a0;
					d_min = d;
					d_issink = j->is_sink;
				}

				for (j=a0->head; j->TS!=TIME; j=j->parent->head)
				{
					j -> TS = TIME;
					j -> DIST = d --;
				}
			}
		}
	}

	if (i->parent = a0_min)
	{
		i -> TS = TIME;
		i -> DIST = d_min + 1;
		i->is_sink = d_issink;
		
		if (d_issink==0)
		{
			/* process neighbors */
			for (a0=i->first; a0; a0=a0->next)
			{
				j = a0 -> head;
				if (j->is_sink && (a=j->parent))
				{
					if (a0->r_cap) set_active(j);
					if (a!=TERMINAL && a!=ORPHAN && a->head==i)
					{
						/* add j to the adoption list */
						j -> parent = ORPHAN;
						np = nodeptr_block -> New();
						np -> ptr = j;
						if (orphan_last) orphan_last -> next = np;
						else             orphan_first        = np;
						orphan_last = np;
						np -> next = NULL;
					}
				}
			}
		}
	}
	else
	{
		/* no parent is found */
		i -> TS = 0;

		/* process neighbors */
		for (a0=i->first; a0; a0=a0->next)
		{
			j = a0 -> head;
			if (j->is_sink && (a=j->parent))
			{
				if (a0->r_cap) set_active(j);
				if (a!=TERMINAL && a!=ORPHAN && a->head==i)
				{
					/* add j to the adoption list */
					j -> parent = ORPHAN;
					np = nodeptr_block -> New();
					np -> ptr = j;
					if (orphan_last) orphan_last -> next = np;
					else             orphan_first        = np;
					orphan_last = np;
					np -> next = NULL;
				}
			}
		}
	}
}
/***********************************************************************/