/*=========================================================================
cmv_region.h
-------------------------------------------------------------------------
Implementation of region operations for CMVision
-------------------------------------------------------------------------
Copyright 2001, 2002
James R. Bruce (jbruce <at> cs.cmu.edu)
School of Computer Science
Carnegie Mellon University
-------------------------------------------------------------------------
This source code is distributed "as is" with absolutely no warranty.
It is covered under the GNU General Public Licence, Version 2.0;
See COPYING, which should be included with this distribution.
-------------------------------------------------------------------------
Revision History:
=========================================================================*/
#ifndef __CMV_REGION_H__
#define __CMV_REGION_H__
#include "cmv_types.h"
namespace CMVision{
//==== Utility Functions ===========================================//
// sum of integers over range [x,x+w)
inline int range_sum(int x,int w)
{
return(w*(2*x + w-1) / 2);
}
// table used by bottom_bit
const int log2modp[37] = {
0, 1, 2,27, 3,24,28, 0, 4,17,25,31,29,12, 0,14, 5, 8,18,
0,26,23,32,16,30,11,13, 7, 0,22,15,10, 6,21, 9,20,19
};
// returns index of least significant set bit
template <class num>
inline int bottom_bit(num n)
{
return(log2modp[(n & -n) % 37]);
}
// returns index of most significant set bit
template <class num>
inline num top_bit(num n)
{
/*
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
n = n - (n >> 1);
return(log2modp[n % 37]);
*/
n |= (n >> 1) | (n >> 2) | (n >> 3);
n |= (n >> 4) | (n >> 8) | (n >> 12);
n |= (n >> 16);
n -= (n >> 1);
return(log2modp[n % 37]);
/*
int i = 1;
if(!n) return(0);
while(n>>i) i++;
return(i);
*/
}
//==== Main Library Functions ======================================//
#include "colors.h"
template <class rle_t,class pixel>
yuv AverageColor(pixel *buf,int width,int height,
rle_t *rmap,int start_index)
{
yuvi sum;
yuv avg;
rle_t r;
pixel p;
int i,x,y,area;
int n = 0;
sum.y = sum.u = sum.v = 0;
area = 0;
i = start_index;
while(i >= 0){
r = rmap[i];
y = r.y;
for(x=r.x; x<r.x+r.width; x+=2){
p = buf[(y*width + x)/2];
// printf("(%d,%d) ",x,y);
sum.y += p.y1 + p.y2;
sum.u += p.u;
sum.v += p.v;
}
area += r.width;
i = r.next;
n++;
}
avg.y = sum.y / area;
avg.u = 2 * sum.u / area;
avg.v = 2 * sum.v / area;
// printf("\n%d : %d %d %d\n",area,avg.y,avg.u,avg.v);
return(avg);
}
template <class rle_t,class tmap_t>
int EncodeRuns(rle_t *rle,tmap_t *map,int width,int height,int max_runs)
// Changes the flat array version of the thresholded image into a run
// length encoded version, which speeds up later processing since we
// only have to look at the points where values change.
{
tmap_t m,save;
tmap_t *row;
int x,y,j,l;
rle_t r;
r.next = 0;
// initialize terminator restore
save = map[0];
j = 0;
for(y=0; y<height; y++){
row = &map[y * width];
// restore previous terminator and store next
// one in the first pixel on the next row
row[0] = save;
save = row[width];
row[width] = 15;
r.y = y;
x = 0;
while(x < width){
m = row[x];
r.x = x;
l = x;
while(row[x] == m) x++;
if(m!=0 || x>=width){
r.color = m;
r.width = x - l;
r.parent = j;
rle[j++] = r;
// printf("run (%d,%d):%d %d\n",r.x,r.y,r.width,r.color);
if(j >= max_runs) return(j);
}
}
}
return(j);
}
template <class rle_t>
void ConnectComponents(rle_t *map,int num)
// Connect components using four-connecteness so that the runs each
// identify the global parent of the connected region they are a part
// of. It does this by scanning adjacent rows and merging where
// similar colors overlap. Used to be union by rank w/ path
// compression, but now is just uses path compression as the global
// parent index is a simpler rank bound in practice.
// WARNING: This code is complicated. I'm pretty sure it's a correct
// implementation, but minor changes can easily cause big problems.
// Read the papers on this library and have a good understanding of
// tree-based union find before you touch it
{
int l1,l2;
rle_t r1,r2;
int i,j,s;
// l2 starts on first scan line, l1 starts on second
l2 = 0;
l1 = 1;
while(map[l1].y == 0) l1++; // skip first line
// Do rest in lock step
r1 = map[l1];
r2 = map[l2];
s = l1;
while(l1 < num){
/*
printf("%6d:(%3d,%3d,%3d) %6d:(%3d,%3d,%3d)\n",
l1,r1.x,r1.y,r1.width,
l2,r2.x,r2.y,r2.width);
*/
if(r1.color==r2.color && r1.color){
// case 1: r2.x <= r1.x < r2.x + r2.width
// case 2: r1.x <= r2.x < r1.x + r1.width
if((r2.x<=r1.x && r1.x<r2.x+r2.width) ||
(r1.x<=r2.x && r2.x<r1.x+r1.width)){
if(s != l1){
// if we didn't have a parent already, just take this one
map[l1].parent = r1.parent = r2.parent;
s = l1;
}else if(r1.parent != r2.parent){
// otherwise union two parents if they are different
// find terminal roots of each path up tree
i = r1.parent;
while(i != map[i].parent) i = map[i].parent;
j = r2.parent;
while(j != map[j].parent) j = map[j].parent;
// union and compress paths; use smaller of two possible
// representative indicies to preserve DAG property
if(i < j){
map[j].parent = i;
map[l1].parent = map[l2].parent = r1.parent = r2.parent = i;
}else{
map[i].parent = j;
map[l1].parent = map[l2].parent = r1.parent = r2.parent = j;
}
}
}
}
// Move to next point where values may change
i = (r2.x + r2.width) - (r1.x + r1.width);
if(i >= 0) r1 = map[++l1];
if(i <= 0) r2 = map[++l2];
}
// Now we need to compress all parent paths
for(i=0; i<num; i++){
j = map[i].parent;
map[i].parent = map[j].parent;
}
}
template <class region_t,class rle_t>
int ExtractRegions(region_t *reg,int max_reg,rle_t *rmap,int num)
// Takes the list of runs and formats them into a region table,
// gathering the various statistics along the way. num is the number
// of runs in the rmap array, and the number of unique regions in
// reg[] (bounded by max_reg) is returned. Implemented as a single
// pass over the array of runs.
{
int b,i,n,a;
rle_t r;
n = 0;
for(i=0; i<num; i++){
if(rmap[i].color){
r = rmap[i];
if(r.parent == i){
// Add new region if this run is a root (i.e. self parented)
rmap[i].parent = b = n; // renumber to point to region id
reg[b].color = r.color;
reg[b].area = r.width;
reg[b].x1 = r.x;
reg[b].y1 = r.y;
reg[b].x2 = r.x + r.width;
reg[b].y2 = r.y;
reg[b].cen_x = range_sum(r.x,r.width);
reg[b].cen_y = r.y * r.width;
reg[b].run_start = i;
reg[b].iterator_id = i; // temporarily use to store last run
n++;
if(n >= max_reg) return(max_reg);
}else{
// Otherwise update region stats incrementally
b = rmap[r.parent].parent;
rmap[i].parent = b; // update parent to identify region id
reg[b].area += r.width;
reg[b].x2 = max(r.x + r.width,reg[b].x2);
reg[b].x1 = min((int)r.x,reg[b].x1);
reg[b].y2 = r.y; // last set by lowest run
reg[b].cen_x += range_sum(r.x,r.width);
reg[b].cen_y += r.y * r.width;
// set previous run to point to this one as next
rmap[reg[b].iterator_id].next = i;
reg[b].iterator_id = i;
}
}
}
// calculate centroids from stored sums
for(i=0; i<n; i++){
a = reg[i].area;
reg[i].cen_x = (float)reg[i].cen_x / a;
评论0