影像處理技術目前正積極發展於許多的多媒體設備，像是監視器、平板電腦、智慧型手機、個人行動助理、以及數位相機。在許多影像處理的應用中，每個像素的鄰域資訊可用來評估機率統計資料。然而，傳統的消耗式區域搜尋方式大幅地增加了整體的計算量。因此，本篇論文藉由使用影像的空間冗於性而提出一種非常有效率的O(1)直方圖建立方法。

對輸入影像每一列的像素，本論文所提出之直方圖橫跨數個相鄰行而被計算。隨著掃描列的推進，該直方圖能夠在常數時間內(O(1))使用列資訊間的空間差值做更新。此外，該直方圖的所有元素皆能被視為影像像素的區域統計資訊。相較於其他現行的直方圖建立方法，本文所使用的直方圖資料結構具備像素間的獨立性使得本文方法十分地易於平行化處理。因此，本篇論文也描述了所提出方法的平行化實現方式。

實驗結果指出，本論文提出的方法能夠比數種現行的方法更為快速，因此更加適用於廣泛的影像處理應用之中。

Image processing techniques are currently developing for many multimedia devices, such as the monitor, Tablet PC, smart phone, Personal Digital Assistant (PDA), and digital camera. In many image processing applications, the statistical data of neighbors can be utilized for each pixel. However, the exhaustive search of neighborhood extremely increases the additional cost of the computation. Therefore, this thesis proposes a very efficient O(1) histogram construction method by using the spatial redundancy.

For each row, the constructed histogram is calculated across adjacent columns. After the scanned line moves downward, the histogram can be updated in constant time using the spatial difference between rows. Furthermore, all elements of the proposed histogram can be directly regarded as the kernel histogram of the image processing. Compared with other state-of-the-art methods, the histogram constructed by the proposed method can be easily employed in parallel due to the data independence. Hence, this thesis also describes the parallel implementation of the proposed method.

Experimental results demonstrate that the efficiency of the proposed method in contrast with those of other methods for histogram construction and image processing applications.

[1] Y.-T. Chen and C.-S. Chen, Fast human detection using a novel boosted cascading structure with meta stages, IEEE Trans. Image Process., vol. 17, no. 18, pp. 1452-1464, Aug. 2008.

[2] O. Tuzel, F. Porikli, and P. Meer, Pedestrian detection via classification on Riemannian manifolds, IEEE Trans. Pattern Anal. Mach. Intell., vol. 30, no. 10, pp. 1713-1727, Oct. 2008.

[3] Q. Luo, X. Kong, G. Zeng, and J. Fan, Human action detection via boosted local motion histograms, Mach. Vis. Appl., vol. 21, no. 3, pp. 377-389, Apr. 2010.

[4] D.-Y. Chen, Orientation filter enhanced pedestrian detection, Electron. Lett., vol. 46, no. 20, pp. 1377-1379, Sep. 2010.

[5] F.-C. Cheng, S.-C. Huang, and S.-J. Ruan, Foreground-adaptive motion detection in broad surveillance environments, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E93-A, no.11, pp. 2096-2097, Nov. 2010.

[6] B. Zhang, Y. Gao, S. Zhao, and B. Zhong, Kernel similarity modeling of texture pattern flow for motion detection in complex background, IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 1, pp. 29-38, Jan. 2011.

[7] F.-C. Cheng, S.-C. Huang, and S.-J. Ruan, Scene analysis for object detection in advanced surveillance systems using Laplacian distribution model, IEEE Trans. Syst. Man Cybern. Part C-Appl. Rev., vol. 1, no. 5, pp. 589-598, Sep. 2011.

[8] F.-C. Cheng, S.-C. Huang, and S.-J. Ruan, Illumination-sensitive background modelling approach for accurate moving object detection, IEEE Trans. Broadcast., vol. 57, no. 4, pp. 794-801, Dec. 2011.

[9] F.-C. Cheng and S.-J. Ruan, Accurate motion detection using a self-adaptive background matching framework, IEEE Trans. Intell. Transp. Syst., vol. 13, no. 2, pp. 671-679, Jun. 2012.

[10] F. Porikli, Achieving real-time object detection and tracking under extreme conditions, J. Real-Time Image Proc., vol. 1, no. 1, pp. 33-40, 2006.

[11] L. Peihua, A clustering-based color model and integral images for fast object tracking, Signal Process.: Image Commun., vol. 21, no. 8, pp. 676-687, Sep. 2006.

[12] H. Wang, D. Suter, K. Schindler, and C. Shen, Adaptive object tracking based on an effective appearance filter, IEEE Trans. Pattern Anal. Mach. Intell., vol. 29, no. 9, pp. 1661-1667, Sep. 2007.

[13] J. Wang and Y. Yagi, Adaptive mean-shift tracking with auxiliary particles, IEEE Trans. Syst., Man, Cybern. B: Cybern., vol. 39, no. 6, pp. 1578-1589, Dec. 2009.

[14] H. Medeiros, G. Holguin, P. J. Shin, and J. Park, A parallel histogram-based particle filter for object tracking on SIMD-based smart cameras, Comput. Vis. Image Understand., vol. 114, no. 11, pp. 1264-1272, Nov. 2010.

[15] S. M. Shahed Nejhum, J. Ho, M.-H. Yang, Online visual tracking with histograms and articulating blocks, Comput. Vis. Image Understand., vol. 114, no. 8, pp. 901-914, Aug. 2010.

[16] G. Doretto, T. Sebastian, P. Tu, J. Rittscher, Appearance-based person reidentification in camera networks: problem overview and current approaches, J. Ambient Intell. Human Comput., vol. 2, no. 2, pp. 127-151, Jun. 2011.

[17] P. Dunne and B. Matuszewski, Choice of similarity measure, likelihood function and parameters for histogram based particle filter tracking in CCTV grey scale video, Image Vis. Comput., vol. 29, no. 2-3, pp. 178-189, Feb. 2011.

[18] H. Ning, T. X. Han, D. B. Walther, M. Liu, and T. S. Huang, Hierarchical space-time model enabling efficient search for human actions, IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 6, pp. 808-820, Jun. 2009.

[19] J. Shotton, J. Winn, C. Rother, A. Criminisi, TextonBoost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout, and context, Int. J. Comput. Vis., vol. 81, no. 1, pp. 2-23, Jan. 2009.

[20] A. Ruta, Y. Li, and X. Liu, Robust class similarity measure for traffic sign recognition, IEEE Trans. Intell. Transp. Syst., vol. 11, no. 4, pp. 846-855, Dec. 2010.

[21] A. Yao, G. Wang, X. Lin, and X. Chai, An incremental Bhattacharyya dissimilarity measure for particle filtering, Pattern Recognit., vol. 43, no. 4, pp. 1244-1256, Apr. 2010.

[22] E. Tola, V. Lepetit, and P. Fua, DAISY: An efficient dense descriptor applied to wide-baseline stereo, IEEE Trans. Pattern Anal. Mach. Intell., vol. 32, no. 5, pp. 815-830, May 2010.

[23] C. H. Lampert, M. B. Blaschko, and T. Hofmann, Efficient subwindow search: A branch and bound framework for object localization, IEEE Trans. Pattern Anal. Mach. Intell., vol. 31, no. 12, pp. 2129-2142, Dec. 2009.

[24] T. Kozakaya, T. Shibata, M. Yuasa, and O. Yamaguchi, Facial feature localization using weighted vector concentration approach, Image Vis. Comput., vol. 28, no. 5, pp. 772-780, May 2010.

[25] S. Battiato, G. M. Farinella, G. Gallo, and D. Ravi, Exploiting textons distributions on spatial hierarchy for scene classification, EURASIP J. Image Video Process., vol. 2010, 13 pages, Article ID 919367.

[26] R. Poppe, Example-based human pose recovery under predicted partial occlusions, Stud. Comput. Intell., vol. 281, pp. 327-354, 2010.

[27] M. J. Huang and W.-H. Sheu, Histogram-data-orientated filter for inconsistency removal of interferometric phase maps, Opt. Eng., vol. 44, no. 4, pp. 1-11, Apr. 2005.

[28] P. Rakwatin, W. Takeuchi, and Y. Yasuoka, Stripe noise reduction in MODIS data by combining histogram matching with facet filter, IEEE Trans. Geosci. Remote Sens., vol. 45, no. 6, pp. 1844-1855, Jun. 2007.

[29] F. Porikli, Constant time O(1) bilateral filtering, IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2008, pp. 1-8.

[30] Y. Wan, Q. Chen, and Y. Yang, Robust impulse noise variance estimation based on image histogram, IEEE Signal Process. Lett., vol. 17, no. 5, pp. 485-488, May 2010.

[31] M. Kass and J. Solomon, Smoothed local histogram filters, ACM Trans. Graph., vol. 29, no. 4, pp. 100:1-100:10, Jul. 2010.

[32] R. Schettini, F. Gasparini, S. Corchs, F. Marini, A. Capra, and A. Castorina, Contrast image correction method, J. Electron. Imaging, vol. 19, no. 2, 023005, Apr.-Jun. 2010.

[33] F.-C. Cheng and S.-J. Ruan, Image quality analysis of a novel histogram equalization method for image contrast enhancement, IEEE Trans. Intell. Transp. Syst., vol. E93-D, no. 7, pp. 1773-1779, Jul. 2010.

[34] B. Liu, W. Jin, Y. Chen, C. Liu, and L. Li, Contrast enhancement using non-overlapped sub-blocks and local histogram projection, IEEE Trans. Consum. Electron., vol. 57, no. 2, pp. 583-588, May 2011.

[35] F.-C. Cheng, S.-J. Ruan, and C.-H. Lin, Color contrast enhancement using automatic weighting mean-separated histogram equalization with spherical color model, Int. J. Innov. Comp. Inf. Control, vol. 7, no.8, pp. 5377-5387, Aug. 2011.

[36] T. Celik and T. Tjahjadi, Contextual and variational contrast enhancement, IEEE Trans. Image Process., vol. 20, no. 12, pp. 3431-3441, Dec. 2011.

[37] J.-H. Wang, W.-J. Liu, and L.-D. Lin, Histogram-based fuzzy filter for image restoration, IEEE Trans. Syst., Man, Cybern. B: Cybern., vol. 32, no. 2, pp. 230-238, Apr. 2002.

[38] E. Bratsolis and M. Sigelle, Fast SAR image restoration, segmentation, and detection of high-reflectance regions, IEEE Trans. Geosci. Remote Sens., vol. 41, no. 12, pp. 2890-2899, Dec. 2003.

[39] S. Schulte, V. D. Witte, M. Nachtegael, D. V. Weken, and E. E. Kerre, Histogram-based fuzzy colour filter for image restoration, Image Vis. Comput., vol. 25, no. 9, pp. 1377-1390, Sep. 2007.

[40] P. Rakwatin, W. Takeuchi, and Y. Yasuoka, Restoration of Aqua MODIS band 6 using histogram matching and local least squares fitting, IEEE Trans. Geosci. Remote Sens., vol. 47, no. 2, pp. 613-626, Feb. 2009.

[41] T.-J. Chen, K.-S. Chuang, J.-H. Chang, Y.-H. Shiao, and C.-C. Chuang, A blurring index for medical images, J. Digit. Imaging, vol. 19, no. 2, pp. 118-125, Jun. 2006.

[42] A. E. Shortt, T. J. Naughton, and B. Javidi, Histogram approaches for lossy compression of digital holograms of three-dimensional objects, IEEE Trans. Image Process., vol. 16, no. 6, pp. 1548-1556, Jun. 2007.

[43] P. Tsai, Histogram-based reversible data hiding for vector quantisation-compressed images, IET Image Process., vol. 3, no. 2, pp. 100-114, 2009.

[44] R. Fattal, Single image dehazing, ACM Trans. Graph., vol. 27, no. 3, pp. 72:1-72:9, Aug. 2008.

[45] N. Hautière, J.-P. Tarel, and D. Aubert, Mitigation of visibility loss for advanced camera-based driver assistance, IEEE Trans. Intell. Transp. Syst., vol. 11, no. 2, pp. 474-484, Jun. 2010.

[46] K. He, J. Sun, and X. Tang, Single image haze removal using dark channel prior, IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 12, pp. 2341-2353, Dec. 2011.

[47] T. S. Huang, G. J. Yang, and G. Y. Tang, A fast two-dimensional median filtering algorithm, IEEE Trans. Acoust. Speech Signal Process., vol. ASSP-27, no. 1, pp. 13-18, Feb. 1979.

[48] F. Porikli, Integral histogram: A fast way to extract histograms in Cartesian spaces, in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), vol. I, 2005, pp. 829-837.

[49] S. Perreault and P. Hébert, Median filtering in constant time, IEEE Trans. Image Process., vol. 16, no. 9, pp. 2389-2394, Sep. 2007.

[50] M. Sizintsev, K. G. Derpanis, and A. Hogue, Histogram-based search: A comparative study, in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2008, pp. 1-8.

[51] Y. Wei and L. Tao, Efficient histogram-based sliding window, in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2010, pp. 3003-3010.

[52] H.-W. Chang and H.-T. Chen, A square-root sampling approach to fast histogram-based search, in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2010, pp. 3043-3049.

[53] S. Dubuisson, Tree-structured image difference for fast histogram and distance between histograms computation, Pattern Recognit. Lett., vol. 32, no. 3, pp. 411-422, Feb. 2011.

[54] T. D. Raty, Survey on contemporary remote surveillance systems for public safety, IEEE Trans. Syst. Man Cybern. Part C-Appl. Rev., vol. 40, no. 5, pp. 493-515, Sep. 2010.

[55] C.-C. Chang, T.-L. Chia, and C.-K. Yang, Modified temporal difference method for change detection, Opt. Eng., vol. 44, no. 2, pp. 1-10, Feb. 2005.

[56] J.-E. Ha and W.-H. Lee, Foreground objects detection using multiple difference images, Opt. Eng., vol. 49, no. 4, pp. 047201, Apr. 2010.

[57] F. Barranco, J. Diaz, Eduardo Ros, and B. Pino, Visual system based on artificial retina for motion detection, IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 39, no. 3, pp. 752-762, Jun. 2009.

[58] A. Doshi and A. G. Bors, Smoothing of optical flow using robustified diffusion kernels, Image Vis. Comput., vol. 28, no. 12, pp. 1575-1589, Dec. 2010.

[59] C. Stauffer and W. E. L. Grimson, Adaptive background mixture models for real-time tracking, Proc. IEEE Computer Vision Patt. Recog., pp. 246-252, 1999.

[60] A. Manzanera and J. C. Richefeu, A new motion detection algorithm based on $\Sigma$-$\Delta$ background estimation, Pattern Recognit. Lett., vol. 28, pp. 320-328, Feb. 2007.

[61] D.-M. Tsai and S.-C. Lai, Independent component analysis-based background subtraction for indoor surveillance, IEEE Trans. Image Process., vol. 18, pp. 158-167, Jan. 2009.

[62] C.-H. Ling, C.-W. Lin, C.-W. Su, Y.-S. Chen, and H.-Y. M. Liao, Virtual contour guided video object inpainting using posture mapping and retrieval, IEEE Trans. Multimedia, vol. 13, no. 2, pp. 292-302, Apr. 2011.

[63] J.-M. Guo, Y.-F. Liu, C.-H. Hsia, M.-H. Shih, and C.-S. Hsu, Hierarchical method for foreground detection using codebook model, IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 6, pp. 804-815, Jun. 2011.

[64] J.-M. Guo, C.-C. Lin, M.-F. Wu, C.-H. Chang, and H. Lee, Complexity reduced face detection using probability-based face mask prefiltering and pixel-based hierarchical-feature Adaboosting, IEEE Signal Process. Lett., vol. 18, no. 8, pp. 447-450, Aug. 2011.

[65] Y.-H. Chiu, K.-L. Chung, W.-N. Yang, Y.-H. Huang, and C.-H. Liao, Parameter-free based two-stage method for binarizing degraded document images, Pattern Recognit., DOI: 10.1016/j.patcog.2012.02.023.