/*
* Module: sort_lines
*
* This file contains functions which sort the marks into a
* "readable sequence" Sorts the marks by their y baseline then
* by their x centroid.
*
* Author:
* Stuart Inglis (singlis@internz.co.nz)
* (c) 1998
*/
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "globals.h"
#include "marklist.h"
#include "sort_lines.h"
#include "vector.h"
#include "line.h"
static int cmpint(const void *e1, const void *e2)
{
return ( ((int*)e1) - ((int*)e2) );
}
static int CmpOnY(const void *e1, const void *e2)
{
return ( (((marktype*)e1)->ypos+((marktype*)e1)->h-1)
- (((marktype*)e2)->ypos+((marktype*)e2)->h-1));
}
/* a +ve rotation rotates anti-clockwise from east */
/*
* (100,0) rotated 90 degrees is (100,0)
*
* (0,100)
* |
* |
* |
* |
* |
* --+---------- (100,0)
*
*/
void rot(double *x, double *y, const double theta,
const double cx, const double cy)
{
double xx,yy;
*x-=cx;
*y-=cy;
xx=(*x)*cos(theta) - (*y)*sin(theta);
yy=(*x)*sin(theta) + (*y)*cos(theta);
*x=xx+cx;
*y=yy+cy;
}
void rot_check()
{
double xx,yy;
xx=100; yy=0;
rot(&xx,&yy,DEG2RAD(90),0,0);
if(!(fabs(xx-0)<1e-8) && (fabs(yy-100)<1e-8)){
fprintf(stderr,"rot() violated! %g %g\n",xx,yy);
}
xx=100; yy=0;
rot(&xx,&yy,-DEG2RAD(90),0,0);
if(!(fabs(xx-0)<1e-8) && (fabs(yy+100)<1e-8)){
fprintf(stderr,"rot() violated! %g %g\n",xx,yy);
}
}
marklistptr sortmarks_random(const marklistptr listofmarks,
const int imagew,
const int imageh,
const double rotated_angle,
const int DPI)
{
marklistptr step,listret=NULL;
marktype *row_of_marks=NULL;
marktype *random_rows=NULL;
int i,len,left;
if(listofmarks==NULL)
return NULL;
if((imagew==0) || (imageh==0))
return listofmarks;
assert((rotated_angle>=-180) &&(rotated_angle<=180));
assert(DPI);
len=marklist_length(listofmarks);
CALLOC(row_of_marks,len,marktype);
CALLOC(random_rows,len,marktype);
for(i=0,step=listofmarks; step ;i++,step=step->next){
row_of_marks[i]=marktype_copy(step->data);
}
listret=NULL;
srandom(len);
left=len;
for(i=0;i<len;i++){
int k;
k=random()%left;
random_rows[i]=row_of_marks[k];
row_of_marks[k]=row_of_marks[left-1];
left--;
}
for(i=0; i<len ;i++){
if(listret==NULL)
step=marklist_add(&listret,random_rows[i]);
else
step=marklist_add(&step,random_rows[i]);
}
FREE(row_of_marks);
FREE(random_rows);
return listret;
}
#define NEW_LINE {\
num_lines++;\
REALLOC(lines,num_lines,linetype);\
line_init(&lines[num_lines-1]);\
}
marklistptr sortmarks_profile(const marklistptr listofmarks,
const int imagew,
const int imageh,
const double rotated_angle,
const int DPI)
{
marklistptr step,listret=NULL;
int i,pixels;
int start,end,len;
vectortype profile;
double x,y;
int num_lines=0;
linetype *lines=NULL;
if(listofmarks==NULL)
return NULL;
if((imagew==0) || (imageh==0))
return listofmarks;
assert((rotated_angle>=-180) &&(rotated_angle<=180));
assert(DPI);
len=marklist_length(listofmarks);
pixels=mm2pixels(globals.g_reading_parameter,DPI);
assert(pixels<=10000);
vector_alloc(&profile, imageh*3);
for(step=listofmarks;step;step=step->next){
x=step->data.xpos;
y=step->data.ypos+step->data.h-1;
rot(&x,&y,DEG2RAD(-5),imagew/2.0,imageh/2.0);
assert(imageh+(int)y >=0);
assert(imageh+(int)y < profile.size);
profile.v[imageh+(int)y]++;
}
for(i=0;i<profile.size;i++){
profile.v[i]=(profile.v[i]*profile.v[i]);
}
if(pixels){
vector_convolve(&profile,pixels,RECTANGULAR);
}
vector_norm(&profile);
vector_threshold(&profile,0.3,0,1);
vector_invert(&profile);
vector_mean(&profile);
start=end=0;
while((start<profile.size) && (end<profile.size)){
NEW_LINE;
start=end;
end++;
while((end<profile.size) && (profile.v[end]<0.99)){
end++;
}
for(step=listofmarks;step;step=step->next){
double x,y;
x=step->data.xpos;
y=step->data.ypos+step->data.h-1;
rot(&x,&y,DEG2RAD(-5),imagew/2.0,imageh/2.0);
if((y>=start) && (y<end)){
line_addmark(&lines[num_lines-1],&step->data);
}
}
}
for(i=0;i<num_lines;i++){
line_sort_xpos(&lines[i]);
}
listret=lines_to_listcopy(&lines,num_lines);
for(i=0;i<num_lines;i++)
line_free(&lines[i]);
FREE(lines);
vector_free(&profile);
return listret;
}
marklistptr sortmarks_zhang(const marklistptr listofmarks,
const int imagew,
const int imageh,
const double rotated_angle,
const int DPI)
{
marklistptr step,listret=NULL;
marktype *all_marks=NULL;
int num_lines=0;
linetype *lines=NULL;
int baseline;
int i,len;
if(listofmarks==NULL)
return NULL;
if((imagew==0) || (imageh==0))
return listofmarks;
assert((rotated_angle>=-180) &&(rotated_angle<=180));
assert(DPI);
len=marklist_length(listofmarks);
CALLOC(all_marks,len,marktype);
for(i=0,step=listofmarks; step ;i++,step=step->next){
all_marks[i]=step->data;
}
qsort((void*)all_marks,(unsigned int)len,sizeof(marktype),CmpOnY);
baseline=-1;
for(i=0;i<len;i++){
int t;
t=all_marks[i].ypos;
assert(t>=0);
/* if t is higher than the baseline */
if(t<=baseline){
/* on line */
line_addmark(&lines[num_lines-1],&all_marks[i]);
} else {
/* start of a new line */
NEW_LINE;
baseline=all_marks[i].ypos+all_marks[i].h-1;
line_addmark(&lines[num_lines-1],&all_marks[i]);
}
}
for(i=0;i<num_lines;i++){
line_sort_xpos(&lines[i]);
}
listret=lines_to_listcopy(&lines,num_lines);
for(i=0;i<num_lines;i++)
line_free(&lines[i]);
FREE(lines);
FREE(all_marks);
return listret;
}
#define TENTATIVE 25
marklistptr sortmarks_howard(const marklistptr listofmarks,
const int imagew,
const int imageh,
const double skew_of_page, /* in rads */
const int DPI)
{
marklistptr step,listret=NULL;
marktype *all_marks_rot=NULL;
int baseline;
int i,j;
int num_lines=0;
int len;
int act;
int bots[TENTATIVE];
linetype *lines=NULL;
linetype line_indirect;
rot_check();
if(listofmarks==NULL)
return NULL;
if((imagew==0) || (imageh==0))
return listofmarks;
assert(DPI);
line_init(&line_indirect);
line_add(&line_indirect,listofmarks);
len=marklist_length(listofmarks);
CALLOC(all_marks_rot,len,marktype);
/* assume the input arrives in order of extraction */
for(i=0,step=listofmarks; step ;i++,step=step->next){
double x,y,w,h,oldh;
step->data.symnum=i;
all_marks_rot[i]=step->data;
x=step->data.xpos;
y=step->data.ypos;
/* it's -ve because you want to rotate it the opposite way */
/* but it's -ve that again, because y increases downwards */
rot(&x,&y,skew_of_page,imagew/2.0,imageh/2.0);
all_marks_rot[i].xpos=ROUND(x);
all_marks_rot[i].ypos=ROUND(y);
w=step->data.w;
h=step->data.h;
assert(w && h);
rot(&w,&h,skew_of_page,0,0);
all_marks_rot[i].w=ROUND(w);
if(all_marks_rot[i].w==0){
all_marks_rot[i].w++;
}
if(all_marks_rot[i].h==0){
all_marks_rot[i].h++;
}
all_marks_rot[i].start_of_line=0;
}
qsort((void*)all_marks_rot,(unsigned int)len,sizeof(marktype),CmpOnY);
while(len>0){
act=MIN(TENTATIVE,len);
for(i=0;i<act;i++){
bots[i]=all_marks_rot[i].ypos + all_marks_rot[i].h-1;
}
qsort((void*)bots,(unsigned int)act,sizeof(int),cmpint);
/* find the median */
baseline=bots[act/2];
/* copy the right marks, and remove them from the list */
NEW_LINE;
for(i=0,j=0;j<len;i++,j++){
if(i!=j){
all_marks_rot[i]=all_marks_rot[j];
}
if((all_marks_rot[i].ypos<=baseline) ){
line_addmark(&lines[num_lines-1],&all_marks_rot[i]);
i--;
}
}
len=i;
line_sort_xpos(&lines[num_lines-1]);
line_stats_indirect(&lines[num_lines-1],&line_indirect);
}
/*listret=lines_to_listcopy(&lines,num_lines);*/
listret=lines_to_listcopy_indirect(&lines,&line_indirect,num_lines);
for(i=0;i<num_lines;i++)
line_free(&lines[i]);
FREE(lines);
line_free(&line_indirect);
FREE(all_marks_rot);
return listret;
}