| Binary high-order energy function(BHEF)is an energy function whose order is greater than 2 and the variables are Boolean.Due to its powerful mathematical modeling capabilities,BHEF is widely used in the fields of computer vision and machine learning.However,minimizing BHEFs is a difficult task because of their high-order.To address this issue,a mainstream approach is to transform it into an equivalent quadratic energy function,called equivalent energy function(EEF),and then utilize classical algorithms to minimize the EEF.Although this approach has been successfully applied in multiple tasks such as image denoising and received increasing attention,there is still a lack of in-depth research on the consistency,easy-to-solve property,and more efficient design methods for order reduction.Therefore,in this paper,we explore some issues of BHEFs and order reduction methods,and propose the following main contributions:(1)To guarantee the equivalence of a BHEF and its EEF,the EEF must maintain the same minima as the BHEF,called minima consistency.However,current works only maintain global minima consistency and neglect local minima consistency between the BHEF and its EEF.Since minimizing an EEF is generally NP-hard,its solution in practical applications is most likely a local minimum.Therefore,the local minima consistency is critical for BHEFs to maintain the high-order advantages in modeling problems.In this paper,we analyze the relationship of the minima of the BHEF and its EEF based on the previously defined EEF,and propose a new kind of EEF,called tight equivalent energy function(tight EEF),which shares the same local minima with its BHEF.To maintain local minima consistency between the BHEF and its EEF,we provide two sufficient conditions to determine whether an EEF is a tight EEF.Further,we provide proofs to validate whether an EEF reduced by the state-of-the-art order reduction methods is a tight EEF based on two sufficient conditions.Through comparative experiments,we verify the effectiveness and importance of the tight EEF.(2)The NP-hardness of minimizing the EEF motivates researchers to seek an easyto-solve EEF,and some criteria have been proposed to measure the easy-to-solve property.However,we found experimentally that there are often conflicts between these criteria,and improving a single criterion may lead to the deterioration of other criteria,resulting in a difficult-to-solve EEF.Another critical problem is that some existing reduction methods have great limitations on the order and terms of the BHEF,which greatly limits the domain of vision problems to which BHEFs are applicable.In this paper,we propose a novel order reduction optimization algorithm for BHEFs,which comprehensively considers multiple criteria and ensures that the final produced EEF is a tight EEF.The influences of major factors on the proposed algorithm are comprehensively evaluated by adopting the widely used Fields-of-Experts model.Finally,we show the superiority of our algorithm by comparing it with state-of-the-art order reduction methods.(3)By investigating the consistency and easy-to-solve property of EEFs,the most appropriate order reduction method can be designed for BHEF models in different fields.However,designing order reduction methods is still a challenging task,and existing works have not investigated how to design order reduction methods.In this paper,we study this issue and propose a new framework for designing order reduction methods.Through study,we find that the design difficulty mainly lies in that coefficients and auxiliary variables of the EEF must be set simultaneously.To address this issue,the proposed framework decomposes the design difficulty into two processes,each of which independently considers the coefficients or auxiliary variables of the EEF and ensures that the decomposition remains equivalent to the BHEF.Some valuable properties are also proved.Based on our framework,a new family of 14 order reduction methods are provided.The experiments demonstrate the superiority of our method.(4)In this paper,we extend the application scope of BHEFs and order reduction methods to detect shadows from a single outdoor image,and propose a shadow detection algorithm based on the BHEF.Existing shadow detection algorithms tend to treat shadow regions and shadow edges as independent.However,they depend on each other and constitute a layout information of ”shadow area-shadow edge-non-shadow area”.Based on this layout information,a novel BHEF model is constructed.In addition,to address the issue that dark pixels are misdetected,we further develop the quadratic part of the BHEF.We also rigorously prove the property of the proposed BHEF under the local minimum,and introduce an optimal order reduction method for the BHEF.Experiments show that by effectively combining shadow edge and region information together,the proposed algorithm can efficiently detect shadows from a single outdoor image. |
