Designing efficient catalysts requires correlating surface structure and local chemical composition with reactivity on length scales from nanometers to tens of microns. While much work has been done on this structure/function correlation on single crystals, comparatively little has been done for catalysts of relevance in applications. Such materials are typically highly heterogeneous and thus require methods that allow mapping of the structure/function relationship during electrochemical conversion. Here, we use optical second harmonic imaging combined with cyclic voltammetry to map the surface of gold nanocrystalline and polycrystalline electrodes during electrooxidation and to quantify the spatial extent of surface reconstruction during potential cycling. The wide-field configuration of our microscope allows for real-time imaging of an area similar to 100 mu m in diameter with submicron resolution. By analyzing the voltage dependence of each pixel, we uncover the heterogeneity of the second harmonic signal and quantify the fraction of domains where it follows a positive quadratic dependence with increasing bias. There, the second harmonic intensity is mainly ascribed to electronic polarization contributions at the metal/electrolyte interface. Additionally, we locate areas where the second harmonic signal follows a negative quadratic dependence with increasing bias, which also show the largest changes during successive cyclic voltammetry sweeps as determined by an additional correlation coefficient analysis. We assign these areas to domains of higher roughness that are prone to potential-induced surface restructuring and where anion adsorption occurs at lower potentials than expected based on the cyclic voltammetry.