Image copy detection
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
The success of the Internet and cost-effective digital storage device has made it possible to replicate, transmit, and distribute digital content in an effortless way. Thus, the protection of intellectual Property right (IPR) has become a crucial legal issue. Detecting copies of digital media(images, audio and video) is a basic requirement for IPR protection (or copyright protection).The applications of copydetection include usage tracking and copyright violation enforcement.
For those above purposes, the image copy detection system came out.It aggregated all the images which were viewed as a copy of original image.In this system,an image is partitioned into m×n equalsized blocks,which makes the system independent of input image sizes,and an m×n sub-image is calculated by taking the average value of each block(see Figure.1(b)), This array is converted to a rank matrix as shown in Fig.1(c).Suppose that the intensity values in Fig.1(b) are changed in the copied image so that its sub-image has values:{{30, 60, 40}, {70, 90, 110}, {50, 100, 80}}. Nevertheless,its rank matrix is identical to that shown in Fig. 1(c) and thus perfect matching with original image can be achieved.
Fig.1 (a)An image is divided into m×n blocks (3×3 in this example),(b)average values of blocks, and(c)rank matrix of (b). Let T and Q represent test image and original image,N represent the matrix size;there exists N tuples (t1,q1),…,( tn,qn),…,( tN,qN)(the order of the rank matrix:from left to right and from top to bottom).Now we define D(T,Q) =
measures the distance between the two images(it’s obvious that if D(T,Q) gets smaller while the probability of the test image is considered as a copy of original image by the system becomes larger). Since there are M original images in the image copy detection system(Q1…QM). And the distance between T and some original images is given by D(T,Q1…QM)= 
To make it simple,we want to find an image which owns least D(T,Q1…QM).
For those above purposes, the image copy detection system came out.It aggregated all the images which were viewed as a copy of original image.In this system,an image is partitioned into m×n equalsized blocks,which makes the system independent of input image sizes,and an m×n sub-image is calculated by taking the average value of each block(see Figure.1(b)), This array is converted to a rank matrix as shown in Fig.1(c).Suppose that the intensity values in Fig.1(b) are changed in the copied image so that its sub-image has values:{{30, 60, 40}, {70, 90, 110}, {50, 100, 80}}. Nevertheless,its rank matrix is identical to that shown in Fig. 1(c) and thus perfect matching with original image can be achieved.
Fig.1 (a)An image is divided into m×n blocks (3×3 in this example),(b)average values of blocks, and(c)rank matrix of (b). Let T and Q represent test image and original image,N represent the matrix size;there exists N tuples (t1,q1),…,( tn,qn),…,( tN,qN)(the order of the rank matrix:from left to right and from top to bottom).Now we define D(T,Q) =
measures the distance between the two images(it’s obvious that if D(T,Q) gets smaller while the probability of the test image is considered as a copy of original image by the system becomes larger). Since there are M original images in the image copy detection system(Q1…QM). And the distance between T and some original images is given by D(T,Q1…QM)= To make it simple,we want to find an image which owns least D(T,Q1…QM).Input
The first line of input should give the number of cases, T (at most 100). T test cases follow. The first line of each test case contains two integer n (1 ≤ n ≤ 100) and m(1 ≤ m ≤ 100) indicating the size of rank matrix and number of original images. The following m lines each contains a sequence of n different integers denotes the rank matrix.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the least distance D(T,Q1…QM).
Sample Input
2 3 2 1 2 3 1 3 2 9 3 1 4 2 5 7 9 3 8 6 2 1 4 5 9 3 7 6 8 9 8 7 6 5 4 3 2 1
Sample Output
Case #1: 2 Case #2: 58
Source
2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU