Histogram matching

<h2 id="implementation">Implementation</h2>
Consider a grayscale input image X. It has a probability density function pr(r), where r is a grayscale value, and pr(r) is the probability of that value. This probability can easily be computed from the histogram of the image by

 
 
 
 
 p
 
 r
 
 
 (
 
 r
 
 j
 
 
 )
 =
 
 
 
 n
 
 j
 
 
 n
 
 
 
 
 {\textstyle p_{r}(r_{j})={n_{j} \over n}}

Where nj is the frequency of the grayscale value rj, and n is the total number of pixels in the image.
Now consider a desired output probability density function pz(z). A transformation of pr(r) is needed to convert it to pz(z).

Each pdf (probability density function) can easily be mapped to its cumulative distribution function by

S
        (
        
          r
          
            k
          
        
        )
        =
        
          ∑
          
            j
            =
            0
          
          
            k
          
        
        
          p
          
            r
          
        
        (
        
          r
          
            j
          
        
        )
        ,
        
        k
        =
        0
        ,
        1
        ,
        2
        ,
        3
        ,
        …
        ,
        L
        −
        1
      
    
    {\displaystyle S(r_{k})=\sum _{j=0}^{k}p_{r}(r_{j}),\qquad k=0,1,2,3,\ldots ,L-1}

G
        (
        
          z
          
            k
          
        
        )
        =
        
          ∑
          
            j
            =
            0
          
          
            k
          
        
        
          p
          
            z
          
        
        (
        
          z
          
            j
          
        
        )
        ,
        
        k
        =
        0
        ,
        1
        ,
        2
        ,
        3
        ,
        …
        ,
        L
        −
        1
      
    
    {\displaystyle G(z_{k})=\sum _{j=0}^{k}p_{z}(z_{j}),\qquad k=0,1,2,3,\ldots ,L-1}

Where L is the total number of gray level (256 for a standard image).
The idea is to map each r value in X to the z value that has the same probability in the desired <a href="/facts/Probability_density_function/zvfybna4">pdf</a>. I.e. S(rj) = G(zi) or z = G−1(S(r)).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="example">Example</h2>
The following input grayscale image is to be changed to match the reference histogram.
The input image has the following histogram

It will be matched to this reference histogram to emphasize the lower gray levels.

After matching, the output image has the following histogramAnd looks like this
<h2 id="algorithm">Algorithm</h2>
Given two images, the reference and the target images, we compute their histograms. Following, we calculate the <a href="/facts/Cumulative_distribution_function/WaKU8tp4">cumulative distribution functions</a> of the two images' histograms – 
 
 
 
 
 F
 
 1
 
 
 (
 )
 
 
 
 {\displaystyle F_{1}()\,}
 
 for the reference image and 
 
 
 
 
 F
 
 2
 
 
 (
 )
 
 
 
 {\displaystyle F_{2}()\,}
 
 for the target image. Then for each gray level 
 
 
 
 
 G
 
 1
 
 
 ∈
 [
 0
 ,
 255
 ]
 
 
 {\displaystyle G_{1}\in [0,255]}
 
, we find the gray level 
 
 
 
 
 G
 
 2
 
 
 
 
 
 {\displaystyle G_{2}\,}
 
 for which 
 
 
 
 
 F
 
 1
 
 
 (
 
 G
 
 1
 
 
 )
 =
 
 F
 
 2
 
 
 (
 
 G
 
 2
 
 
 )
 
 
 
 {\displaystyle F_{1}(G_{1})=F_{2}(G_{2})\,}
 
, and this is the result of histogram matching function: 
 
 
 
 M
 (
 
 G
 
 1
 
 
 )
 =
 
 G
 
 2
 
 
 
 
 
 {\displaystyle M(G_{1})=G_{2}\,}
 
. Finally, we apply the function 
 
 
 
 M
 (
 )
 
 
 {\displaystyle M()}
 
 on each pixel of the reference image.

<h2 id="exact-histogram-matching">Exact histogram matching</h2>
In typical real-world applications, with 8-bit pixel values (discrete values in range [0, 255]), histogram matching can only approximate the specified histogram. All pixels of a particular value in the original image must be transformed to just one value in the output image.
Exact histogram matching is the problem of finding a transformation for a discrete image so that its histogram exactly matches the specified histogram.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Several techniques have been proposed for this. One simplistic approach converts the discrete-valued image into a continuous-valued image and adds small random values to each pixel so their values can be ranked without ties. However, this introduces noise to the output image.
Because of this there may be holes or open spots in the output matched histogram.

<h2 id="multiple-histogram-matching">Multiple histogram matching</h2>
The histogram matching algorithm can be extended to find a monotonic mapping between two sets of histograms. Given two sets of histograms 
 
 
 
 P
 =
 {
 
 p
 
 i
 
 
 
 }
 
 i
 =
 1
 
 
 k
 
 
 
 
 {\displaystyle P=\{p_{i}\}_{i=1}^{k}}
 
 and 
 
 
 
 Q
 =
 {
 
 q
 
 i
 
 
 
 }
 
 i
 =
 1
 
 
 k
 
 
 
 
 {\displaystyle Q=\{q_{i}\}_{i=1}^{k}}
 
, the optimal monotonic color mapping 
 
 
 
 M
 
 
 {\displaystyle M}
 
 is calculated to minimize the distance between the two sets simultaneously, namely 
 
 
 
 
 argmin
 
 M
 
 
 ⁡
 
 ∑
 
 k
 
 
 d
 (
 M
 (
 
 p
 
 k
 
 
 )
 ,
 
 q
 
 k
 
 
 )
 
 
 {\displaystyle \operatorname {argmin} _{M}\sum _{k}d(M(p_{k}),q_{k})}
 
 where 
 
 
 
 d
 (
 ⋅
 ,
 ⋅
 )
 
 
 {\displaystyle d(\cdot ,\cdot )}
 
 is a distance metric between two histograms. The optimal solution is calculated using <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Histogram_equalization/vmohr7XK">Histogram equalization</a></li>
<li><a href="/facts/Image_histogram/lfDPwpS2">Image histogram</a></li>
<li><a href="/facts/Color_mapping/sPgHLPKY">Color mapping</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Gonzalez, Rafael C.; Woods, Richard E. (2008). Digital Image Processing (3rd ed.). Prentice Hall. p. 128. ISBN 9780131687288. <a href="9780131687288" target="_blank">9780131687288</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gonzalez, R.C.; Fittes, B.A. (June 9–11, 1975). Gray-level transformations for interactive image enhancement (PDF). 2nd Conference on Remotely Manned Systems: Technology and Applications. Los Angeles, California. pp. 17–19. <a href="https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19770022806.pdf#page=29" target="_blank">https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19770022806.pdf#page=29</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gonzalez, Rafael (2017). Digital image processing 4th Edition. London: Pearson. pp. 94–103. ISBN 978-0133356724. <a href="978-0133356724" target="_blank">978-0133356724</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Coltuc, Dinu; Bolon, Philippe; Chassery, Jean-Marc (May 2006). "Exact Histogram Specification". IEEE Transactions on Image Processing. 15 (5): 1143–52. Bibcode:2006ITIP...15.1143C. doi:10.1109/TIP.2005.864170. PMID 16671295. S2CID 16060881. <a href="https://www.researchgate.net/publication/7109912" target="_blank">https://www.researchgate.net/publication/7109912</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Shapira D.; Avidan S.; Hel-Or Y. (2013). "Multiple Histogram Matching" (PDF). Proceedings of the IEEE International Conference on Image Processing. <a href="http://www.faculty.idc.ac.il/toky/Publications/Conference/hist_icip_13.pdf" target="_blank">http://www.faculty.idc.ac.il/toky/Publications/Conference/hist_icip_13.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Histogram matching open-in-new

Histogram matching