Projects & Code»Efficient histograms on polygons

Efficient Histogram Computation on Polygonal Regions

This is project page for the following paper:

Efficient Computation of Histograms on Densely Overlapped Polygonal Regions
Yuting Zhang, Yueming Wang, Gang Pan, Zhaohui Wu
Neurocomputing, vol. 118, pp. 141-149, 2013. doi: 10.1016/j.neucom.2013.02.027
[] [] [paper] [code]

This paper proposes a novel algorithm to efficiently compute the histograms in densely overlapped polygonal regions. An incremental scheme is used to reduce the computational complexity. By this scheme, only a few entries in an existing histogram need to be updated to obtain a new histogram. The updating procedure makes use of a few histograms attached to the polygon’s edges, which can be efficiently pre-computed in a similar incremental manner. Thus, the overall process can achieve higher computational efficiency. Further, we extend our method to efficiently evaluate objective functions on the histograms in polygonal regions. The experiments on natural images demonstrate the high efficiency of our method. 
@article{2013-neurocomp-polyhist,
  author={Yuting Zhang and Yueming Wang and Gang Pan and Zhaohui Wu},
  title={Efficient Computation of Histograms on Densely Overlapped Polygonal Regions},
  year={2013},
  url={http://www.ytzhang.net/files/publications/2013-neurocomp-polyhist.pdf},
  pages={141-149},
  volume={118},
  doi={10.1016/j.neucom.2013.02.027},
  journal={Neurocomputing},
  issn={0925-2312}
}

1. Code

Code@GitHub: 

Tarball@this site:

2. Main ideas

We propose a novel algorithm to efficiently compute the histograms in densely overlapped polygonal regions. An incremental scheme is used to reduce the computational complexity. By this scheme, only a few entries in an existing histogram need to be updated to obtain a new histogram. The updating procedure makes use of a few histograms attached to the polygon’s edges, which can be efficiently pre-computed in a similar incremental manner. Thus, the overall process can achieve higher computational efficiency. Further, we extend our method to efficiently evaluate objective functions on the histograms in polygonal regions. The experiments on natural images demonstrate the high efficiency of our method.

The diagram of incremental histogram computation in polygonal regions. (a) Positive/negative residual. (b) Edge residuals generated by sliding the polygon. (c) The good edge residual pair for incrementally computing the histograms in edge residuals. (d) The bad edge residual pair with small overlaps and irregular non-overlapped regions between them. (e) The histograms in edge residuals in the first a few rows are directly computed. (f) The histograms in most edge residuals are incrementally computed.