Gareth Rees는 이 질문에 대해 여러 저자를 인용 한 Math Overflow 의 David Eppstein의 답변 을 확장 하는 매우 좋은 답변 을 게시했습니다 . 한 문장에서 최적의 솔루션을 산출하는 알고리즘은 먼저 오목한 정점 사이의 최대 비교 차 선 세트 (이분 그래프에서 최대 독립 세트에 의해 다항식 시간에서 발견됨)를 절단 한 다음 이러한 절단을 탐욕스럽게 확장하여 나머지 면은 직사각형입니다.
이분 그래프에서 MIS를 찾으려면 최대 일치 알고리즘이 필요합니다. 이 작업이 너무 많은 경우 각 오목한 정점에서 수직 절단이 이루어지는 욕심 많은 단계는 2 근사치입니다.
-------------------응용 프로그램에 따라 웨이블릿을 사용하여이 문제를 해결할 수 있습니다. 2D 배열을 회색조 이미지로 생각하면 목표는 직사각형 함수 (예 : Haar 웨이블릿)로 분해하여 압축 한 다음 미세한 세부 사항을 나타내는 데 사용되는 함수를 폐기하는 것입니다. 지금까지 보여 주신 데이터 (즉, 노이즈 나 텍스처가 없음)를 감안할 때 웨이블릿 변환을 수행 한 후 실제로 아무것도 버릴 필요가 없습니다.
파이썬에서 사용할 수있는 http://www.pybytes.com/pywavelets/ ,
import pywt
import numpy as np
import matplotlib.pyplot as plt
import Image
img = Image.open('Desktop/b12nI.png')
plt.imshow(img, cmap='gray')
단일 레벨 이산 웨이블릿 변환을 사용하십시오.
coeffs = pywt.dwt2(img, 'haar')
cA, (cH, cV, cD) = coeffs
는 cA하르의 근사에 사용되는 웨이블릿 계수를 포함한다. 근사치는 데이터에 대해 정확하며 근사 계수에 대한 역변환을 통해 확인할 수 있습니다.
recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(recon - img))
1.4210854715202004e-14를 생성합니다.
비교하기 위해 Haar 웨이블릿을 사용하여 가우시안 노이즈를 근사하려고하면 :
noise = np.random.randn(512,512)
cA, (cH, cV, cD) = pywt.dwt2(noise, 'haar')
recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(noise-recon))
수익률 : 213.31090340487393
계산적으로 웨이블릿 변환은 O (n)입니다.
웨이블릿 변환을위한 Java 코드는 다음과 같습니다 : https://en.wikipedia.org/wiki/Discrete_wavelet_transform
더 많은 정보 : http://gtwavelet.bme.gatech.edu/wp/kidsA.pdf
출처
https://stackoverflow.com/questions/22050205