# Patent

## Title
Privacy-preserving evidence in ALPR applications

## Abstract

A system and method for preserving privacy of evidence are provided. In the method, an encrypted first image is generated by encrypting a first image acquired at a first location with a symmetric cryptographic key that is based on first information such as a license plate number extracted from the first image and first metadata associated with the first image, such as a time at which the first image was acquired. When a link is established between a second image and the first image, for example, through visual signature matching, the symmetric cryptographic key can be reconstructed, without having access to the first image, but based instead on the first metadata and information extracted from the second image. The reconstructed symmetric cryptographic key can then be used for decryption of the encrypted image to establish evidence that the license plate number was indeed extracted from the first image.

## Background
BACKGROUND
The exemplary embodiment relates to object recognition and finds particular application in connection with a system and method for identification of an identifier of a vehicle while maintaining privacy of personal data.
Vehicle identification can be defined as the process of measuring a set of properties of a vehicle with one or multiple sensors and mapping it to a unique identifier. Visual sensors (e.g., cameras) are often used to capture an image containing a license plate and then an Automatic License Plate Recognition (ALPR) process is applied. Given an image containing a vehicle license plate, ALPR systems typically output the license plate number of the vehicle, which constitutes a unique identifier. The recognized identifier can be used for different purposes, such as automatic collection of tolls, enforcement, such as detection of speed violations, management of car parks, data mining for analysis of traffic patterns, and the like.
However, automatic vehicle identification poses some concerns for privacy rights, since the acquirer of the vehicle identifier, such as a car park owner, possesses data that can often be traced to the vehicle owner. There is also a risk that unauthorized persons may be able to access the data and use it for purposes other than the legitimate purposes for which it was collected.
In some countries, therefore, governments and citizens are becoming more concerned about the collection of such data and restrictions are being placed on its collection. The storage of a vehicle identifier in persistent memory has been recognized as a violation of the right to privacy in some European countries. To address this, number plate recognition system have been developed that place each passing vehicle identifier in temporary storage and access it directly in real-time to check for exceptional situations (such as a vehicle exceeding a speed limit). If there is no match, the data is not permanently stored.
Even where there is no government regulation, there is pressure to modify the process of automatic vehicle identification in car parks and other locations, including processing and storage of the identities, in order to preserve the privacy of the car park users.
U.S. patent application Ser. No. 14/054,998, filed Oct. 16, 2013, entitled DELAYED VEHICLE IDENTIFICATION FOR PRIVACY ENFORCEMENT, by Jose-Antonio Rodriguez Serrano, et al., the disclosure of which is incorporated herein by reference in its entirety, discloses a method for matching two license plate regions of two images without requiring recognizing the identity, e.g. the plate number, of the vehicles. The method preserves user privacy to comply with privacy requirements, since ALPR is performed only if some condition is met.
However, some regulations may require that the service operator provides proof that both the timestamp and the image at both locations are valid. This may raise concerns that recording time-stamped images taken at known locations may violate the protection of drivers' privacy, in view of other regulations.
There remains a need for a system and method which provides for the recognition of a unique identifier of an object, such as a vehicle, when a condition is met, and for providing proof of the validity of the underlying evidence used to determine that the condition is met, while at the same time, preserving the privacy of persons associated with the identifier.
INCORPORATION BY REFERENCE
The following references, the disclosures of which are incorporated herein by reference in their entireties, are mentioned:
U.S. Pub. No. 20100226564, entitled FRAMEWORK FOR IMAGE THUMBNAILING BASED ON VISUAL SIMILARITY, by Luca Marchesotti, et al.
U.S. Pub. No. 20120143853, published on Jun. 7, 2012, entitled LARGE-SCALE ASYMMETRIC COMPARISON COMPUTATION FOR BINARY EMBEDDINGS, by Albert Gordo, et al.
U.S. Pub. No. 20130060786, published Mar. 7, 2013, entitled TEXT-BASED SEARCHING OF IMAGE DATA, by Jose Antonio Rodriguez Serrano, et al.
U.S. Pub. No. 20130129151, published May 23, 2013, entitled METHODS AND SYSTEMS FOR IMPROVED LICENSE PLATE SIGNATURE MATCHING BY SIMILARITY LEARNING ON SYNTHETIC IMAGES, by Jose Antonio Rodriguez Serrano, et al.
U.S. Pub. No. 20130129152, published May 23, 2013, entitled METHODS AND SYSTEMS FOR IMPROVING YIELD IN WANTED VEHICLE SEARCHES, by Jose Antonio Rodriguez Serrano, et al.
U.S. Pub. No. 20130182909, published Jul. 18, 2013, entitled IMAGE SEGMENTATION BASED ON APPROXIMATION OF SEGMENTATION SIMILARITY, by Jose Antonio Rodriguez Serrano.
U.S. Pub. No. 20130259314, published Oct. 3, 2013, entitled METHODS AND SYSTEMS FOR ENHANCING THE PERFORMANCE OF AUTOMATED LICENSE PLATE RECOGNITION APPLICATIONS UTILIZING MULTIPLE RESULTS, by Vladimir Kozitsky, et al.
U.S. application Ser. No. 13/527,228, filed Jun. 19, 2012, entitled OCCUPANCY DETECTION FOR MANAGED LANE ENFORCEMENT BASED ON LOCALIZATION AND CLASSIFICATION OF WINDSHIELD IMAGES, by Sandra Skaff, et al.
U.S. application Ser. No. 13/592,961, filed on Aug. 23, 2012, entitled REGION REFOCUSING FOR DATA-DRIVEN OBJECT LOCALIZATION, by Jose Antonio Rodriguez Serrano.
U.S. application Ser. No. 13/757,014, filed on Feb. 1, 2013, entitled LABEL-EMBEDDING FOR TEXT RECOGNITION, by Jose Antonio Rodriguez Serrano, et al.
U.S. application Ser. No. 13/836,310, filed on Mar. 15, 2013, entitled METHODS AND SYSTEM FOR AUTOMATED IN-FIELD HIERARCHICAL TRAINING OF A VEHICLE DETECTION SYSTEM, by Wencheng Wu, et al.
U.S. application Ser. No. 13/903,218, filed May 28, 2013, entitled SYSTEM AND METHOD FOR OCR OUTPUT VERIFICATION, by Jose Antonio Rodriguez Serrano, et al.
U.S. application Ser. No. 13/973,330, filed Aug. 22, 2013, entitled SYSTEM AND METHOD FOR OBJECT TRACKING AND TIMING ACROSS MULTIPLE CAMERA VIEWS, by Edgar A. Bernal, et al.
BRIEF DESCRIPTION
In accordance with one aspect of the exemplary embodiment, a method for preserving privacy of evidence includes receiving an encrypted first image which has been generated by encrypting a first image with a symmetric cryptographic key that is based on first information extracted from the first image and first metadata associated with the first image. A link is established between a second image and the first image. The first metadata is received. Second information is extracted from the second image. The symmetric cryptographic key that was used to encrypt the first image is reconstructed, based on the second information extracted from the second image and the first metadata. The reconstructed symmetric cryptographic key permits the first encrypted image to be decrypted to regenerate the first image.
One or more of the steps of the method can be performed with a processor.
In accordance with another aspect of the exemplary embodiment, a system includes memory which receives an encrypted first image which has been generated by encrypting a first image with a symmetric cryptographic key that is based on first identifier information extracted from the first image and first metadata associated with the first image, the first metadata, and a first visual signature which has been extracted from the first image. A signature matching component compares the first visual signature with a second visual signature extracted from a second image to establish a link between the second image and the first image. An identifier recognition component extracts second identifier information from the second image. A cryptographic key reconstruction component reconstructs the symmetric cryptographic key that was used to encrypt the first image based on the second identifier information extracted from the second image and the first metadata. The reconstructed symmetric cryptographic key permits the first encrypted image to be decrypted to regenerate the first image. At least one processor implements the signature matching component, identifier recognition component, and cryptographic key reconstruction component.
In accordance with another aspect of the exemplary embodiment, a method for preserving privacy of evidence includes, in a first location, capturing a first image of a vehicle and associated first metadata and generating an encrypted first image by encrypting the first image with a symmetric cryptographic key that is based on first identifier information extracted from the first image and the first metadata. In a second location, spaced from the first location, a second image of a vehicle and associated second metadata are captured. In at least one of the second location and a third location, the encrypted first image and the first metadata are received. The method further includes determining that a condition is met based on the first and second metadata and reconstructing the symmetric cryptographic key from the first metadata and the second identifier information extracted from the second image, thereby establishing that the second identifier information matches the first identifier information.
The first image and identifier information extracted at the first location may both be discarded when the encrypted image has been generated so that they are not available to the second or third locations.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a functional block diagram of a system for privacy-preserving identifier recognition in accordance with a first embodiment;
FIG. 2 illustrates components of a first location computer system in the system of FIG. 1;
FIG. 3 illustrates components of a second location computer system in the system of FIG. 1;
FIG. 4 illustrates components of a validation computer system in the system of FIG. 1;
FIG. 5 graphically illustrates a method for privacy-preserving identifier recognition in accordance with a second embodiment;
FIG. 6 (split into FIGS. 6A and 6B) is a flow chart illustrating the method for privacy-preserving identifier recognition of FIG. 5;
FIG. 7 graphically illustrates creation of a shared key at two locations without exchanging the shared key;
FIG. 8 illustrates is a functional block diagram of a system for privacy-preserving identifier recognition in accordance with a third embodiment;
FIG. 9 graphically illustrates a first part of a method for privacy-preserving identifier recognition in accordance with a fourth embodiment;
FIG. 10 graphically illustrates a second part of the method for privacy-preserving identifier recognition in accordance with the fourth embodiment; and
FIG. 11 (split into FIGS. 11A and 11B) is a flow chart illustrating the method for privacy-preserving identifier recognition of FIGS. 9 and 10.



DETAILED DESCRIPTION
application Ser. No. 14/054,998, discloses a method for maintaining privacy of data, such as a vehicle identifier (license plate number), which includes recognition of the identifier when a match between visual signatures extracted from images of vehicles at two locations is established and a condition is met. The present system and method also distinguish between matching signatures and recognizing license plate numbers. In particular, the exemplary method includes matching visual signatures and retrieving metadata (such as a timestamp) associated with a successful match, which can be used to determine whether a condition is met. The exemplary system and method also use a symmetric cryptographic key that is derived from information extracted from the recognized identifier (and associated metadata) which can be reconstructed at a different location, based on the recognized identifier and earlier acquired metadata. The symmetric cryptographic key can be signed with a private key that can be shared by service providers in a secure manner (i.e., without exchanging the private key itself). The exemplary system and method provides a further assurance that evidence used to establish that a condition is met has not been tampered with or falsified.
Vehicle identification may be desired at multiple locations and/or at different times, for example at the entry and exit of a car park or at different points on a road. For the sake of simplification, two locations X and Y which are spaced from each other by a distance D are considered, although it is to be appreciated that X and Y may be at or close to the same location.
In one embodiment, the aim is to find correspondences between the vehicle identities at X and Y, and when a correspondence between two identities has been established, to determine whether a certain condition is met that depends on associated information captured at X and Y. When the condition is met, a specified action is triggered, such as communicating information to law enforcement or to the owner of the vehicle matching the license plate.
For example, in a speed enforcement application, if a correspondence between vehicle identities at X and Y is established from images captured at X and Y, the information associated with the captured images may include timestamps (TX, TY) at which the vehicle was present at X and Y and optionally respective geographical locations (LX, LY), e.g., geographical coordinates of X and Y. The condition checked may be whether the identified vehicle's speed exceeds a threshold. The speed may be the average speed, computed as the distance D between LY and LY divided by the time difference TY−TX. If the condition is met, e.g., the speed exceeds a predefined threshold, the vehicle identifier recognized from the captured image of the vehicle, e.g., at point Y, for example, is used to implement a process, such as generating an alert that the identified vehicle incurred a speed violation and launching an appropriate corresponding process, such as issuance of a speeding ticket.
The exemplary system and method provides for keeping evidence used to determine that the condition that was met, but still preserving user privacy. In particular, the evidence is readable only if the identifier matches and otherwise remains an opaque piece of data. It is assumed that the data owner (e.g., vehicle driver) trusts the service operator to process his or her data.
In one embodiment, an evidence package is created which allows a third party to verify that the condition was met by providing a key which can be used to decrypt an encrypted image of the vehicle acquired at the first and second locations, the key having been derived from information (an identifier) extracted from the image and associated metadata used to determine if the condition is met, and which allows the key to be verified.
The hashing performed in the exemplary methods discussed below is a one way encryption process which generates a hash value (or “hash”) based on at least one (generally, at least two or more) pieces of information. Given the hash value, the original pieces of information cannot be reconstructed (at least not without undue computational expense and a significant number of examples of such data). Where two or more pieces of information are used to form a hash, these are first combined, e.g., concatenated, in a predefined order.
The encryption keys used herein convert the information to binary data that can be represented as a string. The string can be decrypted to regenerate the original information with the same key, in the case of symmetric encryption, or with a different key, in the case of asymmetric encryption.
With reference to FIG. 1, an environment in which a system 10 for privacy-preserving identifier recognition operates is illustrated. Sets 12, 14 of images IX, IY are captured at locations X and Y by image capture devices 16, 18, such as cameras, positioned at these locations. Image capture devices 16, 18, may be configured to capture automatically an image of each vehicle as it passes the respective location, or only some of the vehicles, depending on the application. Each captured image IX, IY includes at least a portion of a vehicle 20, 22 which is capable of moving the distance D between the two locations X,Y, e.g., along a predefined path 24, such as a road, bus route, car park lane, or the like between the two locations. Each image capture device 16, 18, or a separate information capture component 26, 28, captures information 30, 32 associated with the capture of each image, e.g., in the form of image metadata TX, TY, such as a respective timestamp and/or other types of information available. In the exemplary embodiment, location X is upstream on the path from location Y, such that for a given vehicle, image IX and its associated metadata TX is captured earlier in time than image IY and its associated metadata TY.
The system includes computing devices 40, 42, associated with the two locations, each with memory 44, 46, a processor 48, 50, and one or more input/output devices 50, 52, 54, 56 for communication with external devices and/or with each other. These hardware components of the respective computing devices are communicatively connected by a data/control bus 60, 62. Memory 44, 46 store instructions 64, 66 for performing parts of the exemplary method, which are executed by the processors 48, 50. A database 68 is hosted by one of the computing device or by a remote computing device and stores computed image signatures for the images IX and associated metadata TX.
A third computing device 70, e.g., associated with a third location Z, serves as a validating authority, and includes memory 72, a processor 74 and one or more input/output devices 76, 78, all communicatively connected by a data/control bus 80. Memory 72 stores instructions 82 for performing validation in the exemplary method, which are executed by the processor 74. Computing devices may communicate with the image capture devices 16, 18, database, and each other via wired or wireless links 83, 84, 86, 86, 87, 88, such as a telephone line, local area network, or a wide area network, such as the Internet.
FIGS. 2-4 illustrate exemplary software components of these computing devices, as discussed with reference to FIGS. 5 and 6.
With reference to FIG. 2, the instructions 64 include a signature computation component 90 for computing a visual signature VX 92 based on image IX, an identifier recognition component 94, e.g., which performs ALPR on image IX to generate an identifier PX 96, a one-way encryption component (hashing component) 98, for computing a hash HX 100 of (PX, TX), an encryption key generation component 102, for generating a symmetric cryptographic key KX 104 from HX using a private key Kpriv 106, which may be stored in memory 44, an image encryption component 108, which encrypts image IX using symmetric cryptographic key KX to generate an encrypted image IX′ 110, which may be stored in the database 68.
The signature computation component 90 may include a cropping component which automatically extracts a cropped image 112 from the received image IX 12, which is predicted to include an object of interest (e.g., the area including the license plate number). The signature computation component 90 then computes the visual signature, e.g., based solely on the pixels of the cropped region (or a further cropped region). The computed visual signature VX, metadata TX (optionally encrypted) and optionally also encrypted image IX′ are stored in the database 68. The database 68 may be periodically purged to remove data which is no longer relevant, such as images IX′ and their associated metadata that are out of date, for example, when the condition can no longer be met.
With reference to FIG. 3, the instructions 66 include a signature computation component 120 (analogous to component 90) for computing a visual signature VY 122 based on image IY, an identifier recognition component 124 (analogous to component 94), e.g., which performs ALPR on image IY to generate an identifier PY 126, a one-way encryption component (hashing component) 128 (analogous to component 98), for computing a hash HY 130 of (PY, TX), a cryptographic key reconstruction component 132 (analogous to component 102), for reconstructing a cryptographic key KY 134 from HY using a private key Kpriv 136 (which is the same as the key Kpriv 106), which may be stored in memory 46, an image decryption component 138, which decrypts encrypted image IX′ 110 using cryptographic key KY as a symmetric decryption key to generate a decrypted image 140 (which should be the same as the input image IX), a signature matching component 144, which retrieves signature VX and compares it with signature VY 122 to determine whether there is a match, a condition computation component 146 which determines whether a condition is met, based on TX and TY, and an information processing component 148, which outputs an evidence package 150 based on the information computed by the other components.
The signature computation component 120 may include a cropping component which automatically extracts a cropped image 152 from the received image IY 14, which is predicted to include an object of interest (e.g., the area including the license plate number). The signature computation component 120 then computes the visual signature, e.g., based solely on the pixels of the cropped region (or of a further cropped region). The computed visual signature VY and metadata TY may be stored in memory 46.
As will be appreciated, some preprocessing of the captured images IX, IY may be performed at any time before and/or during the computing of the visual signature, such as scaling, skew removal, reducing the pixel resolution, image enhancement techniques, conversion from color to monochrome, and the like.
The signature matching component 144 accesses the database 68 with each new visual signature VY to identify one or more matching signatures from the visual signatures VX computed for vehicles whose images were previously captured at location X. The signature matching component retrieves the visual signature VX that is the closest match (referred to as V*), together with its associated meta-data TX (referred to as T*).
The identifier recognition component 94, 124 performs character recognition (ALPR) on the image IX or IY, respectively, to generate a character sequence PX or PY respectively corresponding to the recognized identifier of the vehicle, such as the license plate number.
The condition computation component 146 performs a test to determine whether a condition is met, which is a function of TY and T*. For example, component 146 computes an average speed based on the time difference between T* and TY. If the test is satisfied, e.g., if the result of the test is positive, the information processing component 148 outputs the evidence package 150 which confirms that the test has been met. This may include, for example, the automated generation of a notice that a violation has taken place, such as a speeding ticket, unpaid vehicle toll, parking ticket, or the like, depending on the application.
With reference to FIG. 4, the instructions 82 include an image decryption component 160 (analogous to component 120), which receives symmetric cryptographic key KX and decrypts the encrypted image IX′ with KX to obtain the image IX, and an encryption signature verification component 162, which verifies that the symmetric cryptographic key KX is valid by using a public key Kpub 164, provided by the service operator, and the result which is obtained by hashing (PX, TX). A reporting component 166 generates and outputs a validation report 168 which indicates whether the encryption signature is valid and a copy of the images IX and IY and their associated metadata, for use by the owner, government authority responsible for enforcement, or the like.
With reference once more to FIG. 1, the system 10 may be resident on one or more computing devices 40, 42, 70. Each computing device may be a specific or general purpose computing device, such as a PC, such as a desktop, a laptop, palmtop computer, portable digital assistant (PDA), server computer, cellular telephone, tablet computer, pager, combination thereof, or other computing device capable of executing instructions for performing the exemplary method.
The system 10 may communicate, via one or more of input/output interfaces 54, 74, 78, with one or more of a display device 180, such as an LCD screen or computer monitor, for displaying information to users, and a user input device 182, such as a keyboard or touch or writable screen, and/or a cursor control device, such as mouse, trackball, or the like, for inputting text and for communicating user input information and command selections to the respective processor 48, 50. 74. The display device and user input device are illustrated as being part of a client computing device 184, although in other embodiments, they may be directly linked to one of the system computing devices 40, 42, 70.
The memory 44, 46, 72 may represent any type of non-transitory computer readable medium such as random access memory (RAM), read only memory (ROM), magnetic disk or tape, optical disk, flash memory, or holographic memory. In one embodiment, the memory 44, 46, 72 comprises a combination of random access memory and read only memory. In some embodiments, the processor 48, 50, 74 and respective memory 44, 46, 72 may be combined in a single chip.
The network interfaces 52, 54, 56, 58, 76, 78 allow the respective computers to communicate with other devices via a computer network, such as a local area network (LAN) or wide area network (WAN), or the Internet, and may comprise a modulator/demodulator (MODEM) a router, a cable, and and/or Ethernet port.
The digital processors 48, 50, 74 can be variously embodied, such as by a single-core processor, a dual-core processor (or more generally by a multiple-core processor), a digital processor and cooperating math coprocessor, a digital controller, or the like. The digital processor 48, 50, 74, in addition to controlling the operation of the respective computer, executes instructions stored in memory for performing at least a part the method outlined in FIG. 7.
The term “software,” as used herein, is intended to encompass any collection or set of instructions executable by a computer or other digital system so as to configure the computer or other digital system to perform the task that is the intent of the software. The term “software” as used herein is intended to encompass such instructions stored in storage medium such as RAM, a hard disk, optical disk, or so forth, and is also intended to encompass so-called “firmware” that is software stored on a ROM or so forth. Such software may be organized in various ways, and may include software components organized as libraries, Internet-based programs stored on a remote server or so forth, source code, interpretive code, object code, directly executable code, and so forth. It is contemplated that the software may invoke system-level code or calls to other software residing on a server or other location to perform certain functions.
With reference to FIG. 5, an overview of a method for privacy-preserving identifier recognition is illustrated, which shows several steps of one embodiment of the method, described in further detail with respect to FIG. 6.
The method uses encryption methods, such as one or both of asymmetric- and symmetric-key encryption (also called public-key and shared-secret encryption) to provide evidence of the visual capture at location X. Such encryption systems are well known. Specifically, in asymmetric-key encryption, two separate cryptographic keys are employed, one of which is a secret (or private) key and the other of which is a public key, which is mathematically linked to the private key. The public key is used to encrypt the data and to verify a digital signature, while the private key is used to decrypt or to create a digital signature. In symmetric-key encryption the same cryptographic key, or a substantially similar copy thereof, can be used for both encryption and decryption.
There are three main participants in the method in this embodiment:
1) A service operator, e.g., car park operator, toll gate operator, or the like operating at locations X and Y,
2) A verifying authority, e.g., at Z, and
3) A vehicle and, indirectly via the vehicle license plate, the driver and/or owner of the vehicle.
The method begins at S100.
At S102, at location X, a first image IX of a vehicle is acquired, as well as metadata, such as a time TX at which the image IX is captured, by capture device 16, 26.
At S104, a visual signature VX of image IX is computed (e.g., by signature computation component 90). The signature may be stored in database 68, along with TX or TX′ (and/or with a unique EventId).
At S106, identifier recognition, such as ALPR, is performed on IX, obtaining an identifier, such as a license plate number PX (e.g., by identifier recognition component 94).
At S108, the information (PX, TX) is encrypted, e.g., hashed with a one way hash function, to obtain encrypted (hashed) information HX (e.g., by hashing component 98).
At S110, the hash value HX is signed with a private key Kpriv to obtain symmetric cryptographic key KX (e.g., by cryptographic key generation component 102).
At S112, using symmetric encryption key KX, image IX is encrypted, to obtain an encrypted image IX′ (e.g., by image encryption component 108).
At S114, the encrypted image IX′, together with the associated metadata TX and/or TX′ (an encrypted value of TX generated by encrypting TX with, for example, a shared key) are stored in database 68. These can be stored with a unique EventId to make the link with the Signature VX.
At S116, the original image IX as well as PX, HSX, and KX may be discarded and are thus not made available to the second location Y. The method can thus satisfy a requirement that the identifier is not stored but is maintained only transiently for a few seconds or less than a second.
At S118, the encrypted image IX′ may be made public. For example, IX′ can be disclosed to the verifying authority, or to some third party or to anyone since it is encrypted, and neither the operator nor anyone else can decrypt it, other than by breaking the encryption scheme. This ensures that the information contained in the image is private and thus complies with any privacy regulations which may attach to such information. The encrypted image IX′ can later be used to can ensure that the clock used in generating metadata TX in the equipment at location X is correct.
Steps S102 to S118 may be performed at location X, for example, by the computer system 40 at location X, or partly manually, under the control of the service operator.
At S120, at location Y, a new (second) image IY of a vehicle is acquired, as well as metadata, such as a time TY at which the image IY is captured (by capture device 18, 28).
At S122, a visual signature VY of image IY is computed (e.g., by signature computation component 120).
At S124, visual signature matching is performed (e.g., by signature matching component 144), in which VY is compared with one or more signatures VX, received from location X (e.g., retrieved form database 68) to determine whether there is a match.
At S126, if a match is found, the method proceeds to S128, otherwise the method returns to S120 or ends.
At S128, metadata TX is retrieved (or TX′ is retrieved and decrypted to generate TX) and TX and TY are used to determine if a condition is met, e.g., based on a difference between TX and TY and optionally also based on the distance D between the first and second locations, such as whether the vehicle exceeded a predefined speed between X and Y or exceeded an authorized time in a parking lot, or the like (e.g., by condition computation component 146).
At S130, if the condition is met, the method proceeds to S132, otherwise the method returns to S120 or ends.
At S132, identifier recognition, such as ALPR, is performed on IY, obtaining an identifier, such as a license plate number PY (e.g., by identifier recognition component 124).
At S134, the information (PY TX) is encrypted e.g., hashed, with the same one-way hash function as was used for the information (PX, TX), to produce a hash value HY (which should be the same value as HX, if the ALPR has been performed correctly) (e.g., by hashing component 128).
At S136, the hash value HY is signed with the private key KXpriv, to obtain the encryption key KY (which should be the same as KX, assuming that PX and PY are the same) (e.g., by cryptographic key generation component 132).
At S138, the encrypted image IX′ is retrieved and at S140, the encrypted image IX′ is decrypted with KY (which is assumed to be a symmetric key) to obtain image IX (e.g., by decryption component 138).
At S142, an evidence package, which includes IX, IY, TX, and KY is generated and provided to the validation authority and/or to the vehicle owner (e.g., by information processing component 148).
At S144, an action may be initiated, such as notifying the vehicle owner of a violation.
Steps S120 to S144 may be performed at location Y, for example, by the computer system at location Y, or partly manually, under the control of the service operator or a second service operator.
Given the encrypted image IX′, anyone, e.g., the car owner or validation service at location Z, provided with KX can:
a) Decrypt IX′ with KX to obtain IX (S146) and
b) Verify the signature KX by using the service operator's public key Kpub to determine whether HSX is the signature of the result obtained by hashing (PX, TX) (S148). The two values can therefore be compared to see if they are the same and if so, the signature is verified.
The method ends at S150.
The exemplary method can provide several advantages, such as:
a. It allows the operator to provide the image IX taken at location X to the car owner or to the authorities, in a secure way-even though the originally captured digital image has been deleted.
b. It avoids allowing access to this image unless the two visual signatures match.
c. It provides strong evidence that the condition that was met.
As will be appreciated, automated license plate recognition is subject to some errors, particularly when the lighting is poor at the time of image capture. At location Y, an error can be dealt with by a human operator since the image itself is available. At location X, if the license plate was badly recognized, the operator cannot decode image IX′ based on PY, since it is different from PX and thus generates a different hash HY. In some embodiment, the system may attempt various probable variations on PY which are common recognition errors, such as recognizing a zero as a letter O, a letter B as an 8, and so forth, allowing IX′ to be decoded successfully. Only a limited number of accepted permutations may be permitted in this process, to limit the chance that a license plate which does not match is recovered. This procedure may also be performed at location A, in the event that no match is found at location B.
As another alternative, one or both of the hashing components 98, 128 may automatically generate more than one hash value HX, HY (and thus more than one cryptographic key KX, KY), for example, where there are ambiguous characters in the license plate, allowing different permutations to be automatically compared with each other. For example, if the license plate has a letter O, a hash value may be created with both the letter O and the number 0.
Various methods exist for creating and sharing keys between the locations. In one embodiment, Locations X and Y as treated as peers. The two computing devices may each have a public/private key pair, KXpub, KXpriv and KYpub, KYpriv, respectively. The private keys are kept secret and are not shared. The two locations can exchange their public keys with each other and build a shared secret key in a dynamic fashion. For example, as illustrated in FIG. 7, two operators (here illustrated as a service operator and a location operator, but equally applicable to two location operators at X and Y, wish to have a copy 190, 192 of the same secret key Kshared without transmitting it between them, and risking that it will be compromised. The location X operator has a public and private key pair KXpub, KXpriv 194, 196 and the location Y operator has a public and private key pair KYpub with KYpriv 198, 200. The two operators exchange their public keys and combine the remaining keys (KYpub with KXpriv and KXpub with KYpriv) to generate a shared key Kshared_XY which is the same for both. This can be done by using the Diffie-Hellman algorithm, which is a known algorithm for key sharing (or key exchange) between two parties who both own a pair of public and private keys. As result of using this algorithm, both parties will have the same secret key Kshared_XY so that they can continue their private communication using the symmetric encryption which is much faster (in terms of time and computation) than an asymmetric one.
Using this shared secret key Kshared_XY 190, 192, as Kpriv in FIG. 5, they can create the same cryptographic key K (K=KX=KY) in location X and Y, respectively, based on PX (or PY) and TX. Again, the key K is generated by hashing Px and Tx and then encrypting the result (of the hash) with Kshared_XY. K is thus the result of encrypting the hash, as discussed for KX above. This approach avoids the need for a single central public/private key pair.
Publishing IX′ is optional. However, it may help to reinforce the evidence by proving IX was not forged a posteriori. Publishing may include making the information available either to the public at large or to selected people or organizations.
In another embodiment, a service global operator, e.g., car park operator, toll gate operator, or the like is also a party in the method. Five parties can thus be considered: the service global operator at location S; the local operator of location X; the local operator of location Y; the validating authority at location Z; and the car, and indirectly via the vehicle plate the driver and/or owner of the car. The system may be configured as shown in FIG. 8, where similar elements are given the same numerals. This embodiment adds a global service operator computing device 220, with memory 222, storing instructions 224, a processor 226, input/output devices 228, 230 and a bus 232, which be configured as for computing devices 40, 42, etc.
Prior to performing the method:
a. The service operator, at location S, creates a pair of public/private keys KSpub, KSpriv,
b. The operator at location X creates a pair of public/private keys KXpub, KXpriv,
c. The operator at location Y creates a pair of public/private keys KYpub, KYpriv,
d. Each location shares a secret key with the service operator (denoted Kshared_XS and Kshared_YS). This can be done by using the Diffie-Hellman algorithm and the service operator's and the location operator's public and private keys pair (e.g., KXpriv), as illustrated in FIG. 7. As result of using this algorithm, both X and S will have the same secret key Kshared_XS, whereby they can continue their private communication using symmetric encryption which is much faster (in terms of time and computation) than asymmetric.
FIGS. 9 and 10 provide an overview of parts of the exemplary method in this embodiment. FIG. 11 provides a more detailed view of the method, which can be performed with the system of FIG. 8, analogously to the method of FIGS. 6A and 6B, except as noted. Instructions and information generated for performing the method can be stored in the memories 44, 46, 72, 222, in a similar manner to the instructions illustrated in FIGS. 2-4.
At location X, a first image 12 IX and associated metadata 30 TX are captured (S202) (e.g., by capture device 16, 26). A visual signature VX of image IX is generated (S204) (e.g., by signature computation component 90) and stored in memory and/or database 68, along with TX or TX′ (and/or with a unique EventId).
Identifier recognition, such as ALPR is performed on image IX, to obtain a license plate number PX (S206) (e.g., by identifier recognition component 94).
Some or all of the information (LX, IX, PX, TX) is hashed (e.g., by hashing component 98), using a one way hash function, to generate a hash HSX (S208). In the hash, LX is a value which uniquely identifies location X. For this purpose, IX can be the pixel values of the image, a predefined part thereof, or its visual signature. As will be appreciated, given a hash comprising three or more pieces of information together, it is very difficult to reconstruct the original information.
At S210, the hash HSX is signed with the private key for location X, KXpriv, obtaining encryption signature data SX (e.g., by encryption signature generation component 102).
At S212, a random number salt is generated (e.g., using a random number generator 240 (FIG. 2)). A key K is then generated, analogous to KX discussed above, but here based on (PX, TX, salt) and a shared key, such as Kshared_XS. This include hashing (PX, TX, salt), using a one way hash function, to generate a hash value HXS (S214) (e.g., by the hashing component 98), and key-hashing or encrypting HXS with a shared key, such as Kshared_XS (S216), to obtain a symmetric cryptographic key K (e.g., performed by the cryptographic key generation component 102).
At S218, IX is encrypted using a secure symmetric encryption function and K to obtain IX′ (e.g., by component 108).
At S220, information (Salt, TX, LX) may be encrypted using Kpub to obtain M′ (e.g., by component 242).
At S222, (IX, PX, salt, HXs, HSX, K) are discarded.
As additional metadata, the values (IX′, M′) may be stored in association with Tx (or Tx′) and visual signature VX with the same EventId in memory or in database 68 (S224). SX may be disclosed, e.g., to the vehicle owner, the authorities, or another third party (S226).
Steps S202-S226 may be performed by the computer system at location X, or partly manually, under the control of the service operator at location X.
At location Y, the following may be performed:
At S228, a new (second) image IY of a vehicle is acquired, as well as metadata, such as a time TY at which the image IY is captured (e.g., by capture device 18, 28).
At S230, a visual signature VY of image IY is computed (e.g., by component 120).
At S232, visual signature matching is performed in which VY is compared with one or more signatures VX, received from location X to determine whether there is a match (thereby establishing a link between the second image IY and the first image IX) (e.g., by component 144).
At S234, if a match is found, the method proceeds to S236, otherwise the method returns to S228 or ends.
At S236, if there is a match, TX is retrieved and a determination is made as to whether a condition is met based on the metadata TX and TY (e.g., by component 146). This step may be performed at location Y or at the central location, e.g., if TX has been encrypted to form TX′ with the public key KSpub of location S (for example, where location Y does not have the corresponding private key KXpriv for decrypting it).
At S238, if the condition is met, the method proceeds to S240, otherwise the method returns to S228 or ends.
At S240, if there is a match and the condition is met, image IY is encrypted using a symmetric encryption function and Kshared_YS 192, to obtain IY′ (e.g., by an image encryption component 250, FIG. 3).
At S242, encrypted image IY′, together with M′, IX′, retrieved from database 68, are sent to the central operator.
Optionally, at S244, some or all of (LY, IY, TY) can be hashed (e.g., by hashing component 128), to generate a hash HSY and the hash signed using the location Y private key KYpriv to obtain a cryptographic signature SY, which can then be disclosed (S246). Here, LY is an identifier for location Y. IY can be the image itself or the signature VY.
Steps S230-S246 may be performed using the computer system 42 at location Y, or partly manually by the operator.
At the central location S (or at location Y), the following may be performed:
At S248, encrypted image IY′ is decrypted using symmetric key Kshared_YS 190.
At S250, identifier recognition (e.g., ALPR) is performed on image IY, obtaining an identifier PY, such as a license plate number (e.g., by an identifier recognition component analogous to component 124, FIG. 3).
At S252, M′ is decrypted using the private key KSpriv, obtaining (salt, TX, LX).
A key K is generated, based on (PY, TX, salt) and Kshared_XS. This may include hashing (PY, TX, salt) to generate HYS (S254) (which should be the same as HXS, if performed correctly), and encrypting or key-hashing HYS using a shared key Kshared_XS to obtain K (S256).
At S258, encrypted image IX′ can be decrypted using the symmetric key K, to obtain image IX (e.g., by an image decryption component analogous to component 138, FIG. 3).
The information (salt, HYS, K) can be discarded (S260).
At S262, some or all of the following information (PY, LX, IX, TX, LY, IY, TY IX′) can be provided to a third party, such as the validating authority or to the car owner, for example, in a secure way. Steps S250-S262 may be performed using the computer system 220 at location S, or partly manually by the central location operator.
If the evidence is challenged, at S264, the validation authority at Z can check the previously disclosed cryptographic signature SX is valid, using KXpub and the value of hash (LX, IX, PY, TX) since the hash function can be public. A similar validation can be performed for SY with (LY, IY, TY). The validation authority can also check that the condition was met, based on TX and TY, that the encrypted first image Ix′ was generated from the first image IX using K (after reconstructing K), and that K was generated from the first identifier information PX=PY and the metadata TX (and optionally LX), by hashing this information using the hashing function that was used at both X and Y, which can be made public.
The embodiment illustrated in FIGS. 9-11 has several advantages over that of FIGS. 5-6. For example, there is no need for distributing private keys to remote locations and increased security may be achieved when generating the symmetric cryptographic key K by introducing randomness in the form of the salt. Additionally, key K is never disclosed.
In summary, the exemplary method illustrated in FIGS. 5-6 and 9-11 may include:
1. Encrypting an initial (first) image IX with symmetric cryptographic key KX (or K) that is based on information PX extracted from the image and associated metadata TX, to generate an encrypted image IX′;
2. Optionally, publishing an encryption signature SX establishing the existence of the initial image IX, extracted information PX and metadata TX;
3. Discarding the initial image IX, the extracted information PX, and the encryption key KX (or K), while keeping the encrypted image IX′, and an optionally encrypted version of the metadata TX or TX′, in a form that prevents decryption of the encrypted image IX′;
4. Establishing a link (match VX≈VY) between a new (second) image IY and the initial image IX and retrieving the metadata TX associated with initial image IX (optionally, in an encrypted form TX′);
5. Extracting (the same) information PY from the second image IY, decrypting the metadata TX′ (if encrypted) and reconstructing the symmetric cryptographic key KX that was used to encrypt the initial image IX, allowing third party decryption of the encrypted image IX′ to regenerate image IX; and
6. Optionally, producing evidence KXpub, hash(LX, IX, PY, TX) that can be checked by the signature SX produced in step 2. SY can be similarly used as evidence.
7. All these steps can be performed in a decentralized way without the need for exchanging private keys.
The exemplary system and method enable the service operator, e.g., for legal reasons, to provide proof that both the timestamp and the image at both locations are valid, while complying with regulations which require the protection of drivers' privacy. To preserve driver privacy, the evidence is only read when the condition is met, under the assumption that the driver trusts the service operator to process his data. Otherwise the evidence remains as an opaque piece of data.
The methods illustrated in FIGS. 5, 6, and 9-11 may be implemented in computer program products that may be executed on a computer. The computer program products may each comprise a non-transitory computer-readable recording medium on which a control program is recorded (stored), such as a disk, hard drive, or the like. Common forms of non-transitory computer-readable media include, for example, floppy disks, flexible disks, hard disks, magnetic tape, or any other magnetic storage medium, CD-ROM, DVD, or any other optical medium, a RAM, a PROM, an EPROM, a FLASH-EPROM, or other memory chip or cartridge, or any other non-transitory medium from which a computer can read and use. The computer program product may be integral with the computer on which it resides, (for example, an internal hard drive of RAM), or may be separate (for example, an external hard drive operatively connected with the computer), or may be separate and accessed via a digital data network such as a local area network (LAN) or the Internet (for example, as a redundant array of inexpensive of independent disks (RAID) or other network server storage that is indirectly accessed by the computer, via a digital network).
Alternatively, the method may be implemented in transitory media, such as a transmittable carrier wave in which the control program is embodied as a data signal using transmission media, such as acoustic or light waves, such as those generated during radio wave and infrared data communications, and the like.
The exemplary method may be implemented on one or more general purpose computers, special purpose computer(s), a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA, Graphical card CPU (GPU), or PAL, or the like. In general, any device, capable of implementing a finite state machine that is in turn capable of implementing the flowchart shown in FIGS. 5-6 and 9-11, can be used to implement the method. As will be appreciated, while the steps of the method may all be computer implemented, in some embodiments one or more of the steps may be at least partially performed manually.
Further details of some of the steps of the exemplary methods will now be described.
Image and Metadata Capture (S102, S120, S202, S228)
Captured images 12, 14 (IX and IY) may be received by the system 10 in any convenient file format, such as JPEG, GIF, JBIG, BMP, TIFF, or the like or other common file format used for images and which may optionally be converted to another suitable format prior to processing. The input images may be stored in data memory during processing. The images may be individual images, such as photographs, or images extracted from sequences of images, such as video images. In general, each input digital image includes image data for an array of pixels forming the image. The image data may include colorant values, such as grayscale values, for each of a set of color separations, such as L*a*b* or RGB, or be expressed in another other color space in which different colors can be represented. In general, “grayscale” refers to the optical density value of any single color channel, however expressed (L*a*b*, RGB, YCbCr, etc.). The method is also suitable for black and white (monochrome) images. The word “color” is used to refer to any aspect of color which may be specified, including, but not limited to, absolute color values, such as hue, chroma, and lightness, and relative color values, such as differences in hue, chroma, and lightness. In some embodiments, color (i.e., pixel value) can refer to a non-visible region of the electromagnetic spectrum, such as the Near Infrared (NIR) region, which is from about 800 nm to 2500 nm.
The image capture at a given location X, Y may be triggered in any suitable manner. In one embodiment, a loop sensor may be locally positioned, e.g., in the ground, which detects the presence of a vehicle and triggers a shot (and possibly a flash). In one embodiment, the camera 16, 18 shoots a video comprising a sequence of images and a motion detection algorithm or an object detection algorithm (or the combination of both) is employed which detects the presence of a vehicle in the image sequence and selects one image from the sequence accordingly. Vehicle detection techniques are well known and disclosed for example, in U.S. Pat. Nos. 4,433,325, 5,083,200, 5,592,567, 5,809,161, 5,995,900, 6,996,255, and U.S. application Ser. Nos. 13/836,310, and 13/973,330, the disclosures of all of which are incorporated herein in their entireties by reference. The image can be captured in full color, monochrome, NIR (near infrared), or a combination thereof.
In some embodiments, the same image capture device could be used for capturing both images IX and IY, such as in a car park.
The associated metadata 30, 32 may each include sufficient information to enable a determination to be made as to whether a predetermined condition has been met. One or more different types of information may be acquired, such as one or more of time stamp, current speed of the vehicle, GPS location, payment information, weather information, and the like.
Visual Signature Computation (S104, S122, S204, S230)
In the exemplary embodiment, the visual signature VX, VY contains enough information to identify a vehicle (or part of a vehicle) uniquely but should also robust enough to accommodate variations in viewpoint or lighting conditions. It is also constructed in such a way that, given a visual signature, neither the original image nor the identifier can be reconstructed from it.
In the exemplary embodiment, the visual signature VX, VY is extracted from a region of the image which is predicted to contain the identifier such as a region which encompasses the license plate or at least that part of it which includes the license plate number. To identify this region, a detection algorithm that extracts the corresponding part of the image can be run. Methods for identifying the region of interest in the larger image are described, for example, in U.S. Pub. No. 20130182909 and application Ser. No. 13/592,961, incorporated herein by reference.
Once the region of interest has been identified and a cropped image generated which includes this region, the visual signature VX, VY can be computed on the cropped region. In general, the visual signature is a statistical representation of the pixels of the cropped image. For example, a set of patches of the cropped image are extracted, e.g., densely, on a grid at one or at multiple scales. The patches can be obtained by image segmentation, by applying specific interest point detectors, by considering a regular grid, or simply by the random sampling of image patches. In the exemplary embodiment, the patches are extracted on a regular grid, optionally at multiple scales, over the entire cropped image, or at least a part or a majority of the image. For example, at least 10 or at least 20 or at least 50 patches are extracted from each cropped image. Each patch may comprise at least 40 or at least 100 pixels, and up to 1,000,000 pixels or more.
For each patch, low-level features are extracted, such as shape, color and/or gradient (SIFT) features (see, D. Lowe, “Distinctive image features from scale-invariant keypoints”, IJCV, 2004). A patch descriptor, such as a vector or histogram, which is a representation of the extracted low level features for a patch, is generated. Based on the descriptors of all the patches, on overall visual signature of the image is generated. In particular, statistics are computed on these patch descriptors and then the statistics are aggregated.
Each visual signature is a fixed-length vectorial representation of the (cropped) image in a D-dimensional space. In one embodiment, the visual signature is based on the Fisher Vector (FV). See, for example, Perronnin and Dance, “Fisher kernels on visual vocabularies for image categorization,” CVPR, 2007; Perronnin, Sanchez and Mensink, “Improving the Fisher kernel for large-scale image classification”, ECCV, 143-156 (2010); Sanchez and Perronnin, “High-dimensional signature compression for large-scale image classification,” in CVPR 2011; U.S. Pub. No. 20120076401, published Mar. 29, 2012, entitled IMAGE CLASSIFICATION EMPLOYING IMAGE VECTORS COMPRESSED USING VECTOR QUANTIZATION, by Jorge Sanchez, et al.; and U.S. Pub. No. 20120045134, published Feb. 23, 2012, entitled LARGE SCALE IMAGE CLASSIFICATION, by Florent Perronnin, et al. the disclosures of which are incorporated herein by reference in their entireties. The trained GMM is intended to describe the content of any image within a range of interest (for example, any license plate image if the range of interest is license plates). A Fisher Kernel representation can be generated by aggregation of the Fisher vectors. Other image representations may be used such as the bag-of-visual-words of Csurka et al., Visual Categorization with Bags of Keypoints, ECCV Workshop, 2004.
Fisher Vectors show robustness in the range of photometric and geometric variability found in license plate processing. Briefly, Fisher vectors work by aggregating local patch descriptors into a fixed-length representation. First, SIFT descriptors are extracted from patches extracted at multiple scales on a regular grid, and their dimensionality is optionally reduced using principal component analysis (PCA). A visual vocabulary is built by estimating a Gaussian mixture model (GMM) with patch descriptors extracted from a held-out set of images. In other approaches, the local descriptors of the patches of an image are assigned to clusters. For example, a visual vocabulary is previously obtained by clustering local descriptors extracted from training images, using for instance K-means clustering analysis. Each patch vector is then assigned to a nearest cluster and a histogram of the assignments can be generated. In other approaches, a probabilistic framework is employed, as in the case of the Fisher vector described above. For example, it is assumed that there exists an underlying generative model, such as a Gaussian Mixture Model (GMM), from which all the local descriptors are emitted. Each patch can thus be characterized by a vector of weights, one weight for each of a set of (e.g., at least 5 or 10) Gaussian functions forming the mixture model. In this case, the visual vocabulary can be estimated using the Expectation-Maximization (EM) algorithm. In either case, each visual word in the vocabulary corresponds to a grouping of typical low-level features. The visual words may each correspond (approximately) to a mid-level image feature such as a type of visual (rather than digital) object (e.g., features of characters, such as straight lines, curved lines, etc.), characteristic background (e.g., light or dark surface, etc.), or the like. Given an image to be assigned a visual signature, each extracted local descriptor is assigned to its closest visual word in the previously trained vocabulary or to all visual words in a probabilistic manner in the case of a stochastic model. A histogram is computed by accumulating the occurrences of each visual word. The histogram can serve as the visual signature or input to a generative model which outputs a visual signature based thereon.
The Fisher vector is computed as the derivative of the log-likelihood with respect to the GMM parameters. For example, if only the means are considered, it can be shown that the expression is given by:




  
    f
    id
  
  =
  
    
      γ
      ⁡
      
        (
        
          X
          t
        
        )
      
    
    ⁡
    
      [
      
        
          
            x
            
              t
              ,
              d
            
          
          -
          
            m
            
              i
              ,
              d
            
          
        
        
          
            (
            
              S
              
                i
                ,
                d
              
            
            )
          
          2
        
      
      ]
    
  




where y(xt) is the soft-assignment probability of the tth patch to the ith Gaussian, xt,d is the dth component of the ith patch, and mi,d and Si,d are the dth components of the mean and standard deviations of the ith Gaussian, assuming diagonal covariances. Here, i=1 K and d=1 . . . D. If only the derivatives with respect to the mean are used, then the resulting Fisher vector is a concatenation of the K×D elements fid. Square-rooting and l2-normalization of the vector may be used.
To include spatial information about the cropped image, the image can be partitioned into regions, such as at least three regions, the per-patch statistics aggregated at a region level, and then the region-level representations concatenated to form the image representation. See, for example, S. Lazebnik, et al., “Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories,” CVPR '06 Proc. 2006 IEEE Computer Society Conf. on Computer Vision and Pattern Recognition—Volume 2, Pages 2169-2178.
The exemplary visual signatures are of a fixed dimensionality D, i.e., each image representation has the same number of elements. In general, each image representation has at least 30, or at least 60, or at least 100, or at least 500 dimensions, and up to 1000 or more dimensions, each dimension having a respective feature value, which may be reduced to fewer dimensions.
As an example, the low-level features include gradient features, such as SIFT descriptors, one per patch. See, e.g., Lowe, “Distinctive image features from scale-invariant keypoints,” IJCV vol. 60 (2004). In one illustrative example employing SIFT features, the features are extracted from 32×32 pixel patches on regular grids (every 16 pixels) at five scales. The dimensionality of these descriptors can be reduced from 128 to 32 dimensions. Other suitable local descriptors which can be extracted include simple 96-dimensional color features in which a patch is subdivided into 4×4 sub-regions and in each sub-region the mean and standard deviation are computed for the three channels (R, G and B). These are merely illustrative examples, and additional and/or other features can be used. In the examples below, a visual vocabulary of 64 Gaussians is used in the GMM and only the gradient with respect to the mean parameters is considered. The cropped image is split into 4 regions (4 vertical stripes). This results in a 32×64×4=8,192-dimensional FV representation. The representations may be indexed or compressed using conventional techniques (locality sensitive hashing (LSH), product quantization, principal component analysis (PCA), etc.) to speed up the process.
The visual signature is one which does not allow recognition from the identifier from it. A visual signature such as the FV fulfills the desired property that the original image cannot be reconstructed for it, and therefore can be seen as a hash key of the original image as there is no feasible way to recover the original image (or the license plate number) from the visual signature. This is because the identity of the individual patches is lost in the aggregation process. Consequently, this reduces the privacy concern as the service operator does not have access to the identities of all vehicles, only a very small portion of the vehicles that cause the actions to be triggered (e.g., vehicles driving above speed limit). Like hashing functions used for storing passwords, the only method to recover the original image is to try to perform a brute-force match with all possible images.
Other exemplary methods for computing image representations are disclosed for example, in the following references, the disclosures of all of which are incorporated herein in their entireties, by reference: US Pub. Nos. 20030021481; 2007005356; 20070258648; 20080069456; 20080240572; 20080317358; 20090144033; 20090208118; 20100040285; 20100082615; 20100092084; 20100098343; 20100189354; 20100191743; 20100226564; 20100318477; 20110026831; 20110040711; 20110052063; 20110072012; 20110091105; 20110137898; 20110184950; 20120045134; 20120076401; 20120143853, and 20120158739.
Storage (S114, S224)
The signature/metadata pair (VX, TX or TX′) is stored in the database 64 linked together so that the signature matching component 144 can return the associated metadata whenever it finds a match between a signature VX and the visual signature VY of a new image IY.
Visual Search (S124, S232)
Given a query visual signature VY, the database 64 is searched for its closest match(es). The measure of similarity which is used may depend on the type of visual signature employed. The cosine distance has been shown to be an appropriate measure of similarity for the FV. However, other similarity measures are also contemplated, such as the Euclidian distance and the Manhattan distance. The Euclidian distance, dot product, the chi2 distance, Kullback-Leibler (KL) divergence, Jensen-Shannon divergence, and the like may be used in computing similarity for other types of visual signature, for example in the bag-of visual words method.
When the number of visual signatures VX stored in the database 64 is small enough (e.g., on the order of several thousand visual signatures), then the search for a closest match V* can be done in an exhaustive manner, i.e., by comparing the visual query with all database entries. When the database 64 contains a larger number of images, an exhaustive search may be time consuming. In this case, an approximate search technique may be employed. Techniques for the approximate search of high-dimensional vectors are disclosed, for example, in Jégou, et al., “Aggregating local image descriptors into compact codes,” IEEE TPAMI, 34(9)1704-1716 (2012).
Since the Fisher vector is an explicit embedding of the Fisher kernel, the corresponding cosine similarity measure between two such image descriptors VX and VY is the dot product VXTVY. A candidate plate is compared against all images in a database and the identity of the closest match is assigned, provided the similarity is sufficiently high.
In one embodiment, the visual signature (e.g., the FV) can be made more discriminative by applying a projection which is obtained, for instance, by learning a metric for embedding the visual signature into a vectorial space where similarity is a good indicator for actual similarity (in terms of the character sequences forming the identifiers). As an example, a low-rank Mahalanobis metric can be employed, see for example, Rodriguez-Serrano, et al., “Data-Driven Vehicle Identification by Image Matching”. 12th European Conf. on Computer Vision (ECCV) Workshops, Oct. 7-13, 2012, Lecture Notes in Computer Science, vol. 7584, pp. 536-545. See also U.S. application Ser. Nos. 13/592,961, 13/757,014, and Ser. No. 13/903,218, the disclosures of which are incorporated by reference, for descriptions of exemplary embedding techniques. The FV has been shown experimentally to be particularly appropriate for matching of license plate images, especially in combination with learned projections. The Fisher Vector is also shown below to be superior to the standard license plate matching approach which involves in performing ALPR and then comparing the sequences.
Metadata Processing (S128, S236)
The condition computation component 146 may compute various metrics based on the metadata collected at two (or more) locations. For example, the timestamps and GPS coordinates may be used to infer an average speed. This may be compared with a threshold speed, e.g., a maximum speed limit, to determine whether the speed limit is exceeded. In the case of information relating to weather conditions (e.g., a detected rainfall or visibility), this may be used to determine whether the average speed of the vehicle exceeded a weather-related speed limit, which may be lower than the normal posted speed limit.
In some applications images captured at “entries” are associated to “tickets”. Thus the metadata can include a ticket ID, ticket status (paid, non-paid), paid amount, authorized time (e.g., based on the paid amount), and so forth. For example, if a ticket was paid for authorizing the user to park for a time of 2 hours, but the user parked for 4 hours, an unpaid amount may be computed optionally with a penalty. In this case, the test condition applied at S124 may define a relationship between the computed time and the authorized time, for example, to allow for some leeway. For example, the condition may specify that the test is met if the computed time exceeds the authorized time by at least a predetermined amount, such as 5, 10 or 15 minutes, or a percentage of the authorized time.
As will be appreciated, the test may include more than one condition and a given test may require that one or more (or all) of the conditions be satisfied for the test to be met. In some cases, conditions may be evaluated in the alternative. For example, one condition may specify: if condition 1 is satisfied, test condition 2, otherwise test condition 3. Different conditions may rely on the same or different parts of the metadata. For example, one condition could relate to the weather or time of day/day of the week, and another condition to the computed speed of the vehicle, length of stay in the car park, and so forth.
ALPR (S106, S132, S206, S250)
Identifier recognition, such as ALPR, may be performed at the first location X at any time after capture of the image and prior to its encryption. In one embodiment, only if the test performed on the metadata at S128, S236 is positive (e.g., speed greater than a posted speed limit, a parking duration which does not correspond to a paid amount, exiting a car park without paying ticket), then identifier recognition, e.g., ALPR is performed. ALPR may be performed in this case at the second location Y or at a central location S. The ALPR may be performed on image IX, IY before or after cropping or other processing. For example, any suitable ALPR system may be used for recognizing the license plate number in the cropped image. Where multiple images IX, IY are obtained at location X or Y, as in a video sequence, these are considered to be the same as image IX or IY, respectively.
In the case of license plate number recognition, the vehicle identifier (sometimes referred to as a registration or license plate number) includes a sequence of characters drawn from a predefined alphabet (a finite set of characters), such as letters and numbers. The license plate number may be a numeric or alphanumeric code that uniquely identifies the vehicle on which it is mounted within the issuing region's database.
The license plate recognition component 94, 124 may use optical character recognition (OCR) alone or in combination with other techniques, to identify a sequence of characters drawn from the finite alphabet that is predicted to correspond to the characters in the cropped (or original) image IX, IY. Spaces and characters other than those in the finite alphabet may be ignored. In some embodiments, the recognition component 94, 124 may extract additional textual information, such as the state of issuance. Logos may also be recognized from a stored logo database.
As will be appreciated, the license plate number and image of a license plate are exemplary only and are used to illustrate the exemplary embodiment. In other embodiments, a larger set of ASCII, UNICODE, and/or UTF-8 characters may be used as the alphabet. License plate recognition methods which may be used are disclosed, for example, in above-mentioned U.S. Pub. Nos. 20130129151, 20130129152, 20130182909, and 20130259314, and U.S. application Ser. Nos. 13/592,961, 13/757,014, 13/836,310, and 13/903,218, and in J-A. Rodriguez-Serrano, H Sandhawalia, R. Bala, F. Perronnin and C. Saunders, “Data-Driven Vehicle Identification by Image Matching”. 12th European Conf. on Computer Vision (ECCV) Workshops, Oct. 7-13, 2012, Lecture Notes in Computer Science, vol. 7584, pp. 536-545. In one embodiment, Xerox License Plate Recognition (XLPR) software is employed.
Action (S144)
The action initiated by the system may depend on the type of application. In the case of license plates, the action triggered is associated to the respective license plate number identified (e.g., prosecute the violator, alert parking operator, send parking fine, etc.).
Accounting for Imperfect Matching
In some embodiments, it is reasonable to assume that the visual signature matching component 144 delivers 100% accuracy. In such a case, the following operations may be performed:
1. At location X, all the images captured at location X can be discarded after signature computation.
2. At location Y, all the images and signatures of non-violating vehicles can be discarded after S142.
However, a 100% accuracy is not always possible in practice. For example, the following sources of failure may be found. First, the visual signature matching component 144 sometimes does not return any result, for example, because the confidence in the closest match is too low. In such a case, steps S134, etc., are simply not performed. This also means that the corresponding signature which should have been retrieved as V* remains in the database, possibly indefinitely. To avoid the database becoming populated with signatures which may never be needed again, the database may be regularly purged to remove its oldest entries, for example, when they have been in the system for more than a predetermined amount of time. In the case where the condition tested at S128 cannot be met after a predetermined amount of time (for example, the computed speed can no longer exceed the speed limit) the signatures VX which cannot meet the specified condition can be purged.
A second source of failure is a false positive, where the signature matching component 144 may return an incorrect result with a confidence which is higher than a predetermined confidence threshold. This may lead to a vehicle owner erroneously receiving a parking/speeding ticket or other action being taken. In such a case, it may be desirable to ensure that a human operator can correct such an error, when the error becomes known. For example, a procedure may be established for the driver of the vehicle, service provider, or law enforcement to challenge the system. To assist in verifying that a failure has occurred, the encrypted image IX′ may be stored in the database or delivered to the verifying authority in the evidence package. Both IX and IY may be included in the evidence package output at S142. Only the persons who are authorized to access the evidence package (e.g., officers of the law) may have access to the private key needed to decrypt the images.
Uses of the Exemplary System
Examples of where the exemplary system and method may find application include:
1. Point-to-point enforcement, for example speed enforcement on a medium-/long-range.
2. Monitoring entries and exits of car parks. When a vehicle exits the car park, the signature matching component associates its visual signature with the entry transaction. Assuming a ticket is delivered to the customer at the entry, the metadata can include the timestamp, the ticket number, and payment status for that ticket. At the exit, the metadata processing at S128 checks that the ticket has been paid and that the paid amount corresponds to the correct duration. It is also possible to ascertain if the ticket is associated with the same car at entry and exit to avoid ticket swapping. In car parks with barriers, that could trigger an alert to an operator to go and resolve the issue. In car parks without barriers, a fine could be sent to a customer.
In the case of ticket-less parking, when a vehicle exits the car park, the signature matching component associates its visual signature with the entry transaction. When paying the parking fees, the user can associate the visual signature with an information such as license plate number. The metadata can include the timestamp and payment status for that license plate number. At the exit, the metadata processing at S128 checks that the paid amount for the license plate number corresponds to the correct duration. In car parks with barriers, that could trigger an alert to an operator to go and resolve the issue. In car parks without barriers, a fine could be sent to a customer.
3. Automatic tolling: this may include associating the vehicle ID with the bank account/credit card of subscribed drivers for automatic payments.
4. Violation enforcement: this may include associate the violating vehicle ID with the identity of the vehicle owner for prosecution.
5. Car park management: this may include associating the vehicle ID with an issued parking ticket and open a barrier automatically at the car park exit; or associate the vehicle ID to a subscribed customer account and open all barriers automatically.
6. Vehicle flow analysis/data mining: This may include tracking re-occurring vehicle IDs to measure travel times, analyze patterns of behavior, and the like.
It will be appreciated that variants of the above-disclosed and other features and functions, or alternatives thereof, may be combined into many other different systems or applications. Various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.

## Claims

1. A method for preserving privacy of evidence comprising:
receiving an encrypted first image which has been generated by encrypting a first image with a symmetric cryptographic key that is generated by encrypting, with a one way function, first information extracted from the first image and first metadata associated with the first image and signing the encrypted first information and first metadata with a shared key, wherein the first metadata comprises a first time;
establishing a link between a second image and the first image comprising comparing a first visual signature computed based on the first image with a second visual signature computed based on the second image, each of the first and second visual signatures being a statistical representation of pixels of the respective image;
when the visual signatures are found to match, receiving the first metadata;
extracting second information from the second image;
reconstructing the symmetric cryptographic key that was used to encrypt the first image based on the second information extracted from the second image and the first metadata, by encrypting, with the one way function, the second information and the first metadata and signing the encrypted second information and first metadata with the shared key, the reconstructed symmetric cryptographic key permitting the first encrypted image to be decrypted to regenerate the first image,
wherein at least one of the establishing a link between a second image and the first image and the reconstructing of the symmetric cryptographic key is performed with a processor.

2. The method of claim 1, further comprising determining whether a condition is met based on the metadata associated with the first image and metadata assocated with the second image.

3. The method of claim 2, wherein the reconstructing of the symmetric cryptographic key is performed only when the condition is met.

4. The method of claim 1, wherein the information extracted from the first image comprises a first identifier and the information extracted from the second image comprises a second identifier, the reconstructing of the symmetric cryptographic key establishing that the first identifier matches the second identifier.

5. The method of claim 1, wherein the reconstruction of the symmetric cryptographic key comprises hashing the first metadata and the second information.

6. The method of claim 5, further comprising encrypting the hashed first metadata and second information with a shared key.

7. The method of claim 1, further comprising generating the shared key at a first location and at a second location and wherein the symmetric cryptographic key is generated at the first location with the shared private key and the reconstruction of the symmetric cryptographic key is performed at the second location with the shared key.

8. The method of claim 7, wherein the shared key is generated by exchanging a public key of each of first and second key pairs and combining each of the public keys with a private key of the other of the key pairs.

9. The method of claim 1, wherein the first image and symmetric cryptographic key are generated at a first location and the reconstruction is performed at a second location, and wherein the first image and the symmetric cryptographic key generated at the first location are not made available to the second location.

10. The method of claim 1, further comprising outputting an evidence package which includes at least one of:
the first image;
the second image;
the first information;
the second information;
the first metadata;
second metadata associated with the second image, the second metadata comprising a second time, later than the first time; and
a signature produced by hashing at least two of:
the first image,
the first information,
the first metadata, and
a first location identifier identifying a location at which the first image was captured.

11. The method of claim 1, further comprising publishing an encryption signature establishing the existence of the first image, extracted first information, and first metadata.

12. The method of claim 1, wherein the second image is associated with second metadata which comprises a second time, later than the first time.

13. A system comprising:
memory which receives:
an encrypted first image which has been generated by encrypting
a first image with a symmetric cryptographic key that is generated by encrypting, with a one way function, first identifier information extracted from the first image and first metadata associated with the first image and signing the encrypted first information and first metadata with a shared key,
the first metadata, and
a first visual signature which has been extracted from the first image, the first visual signature being a statistical representation of pixels of the first image;

a signature matching component which compares the first visual signature with a second visual signature extracted from a second image to establish a link between the second image and the first image, the second visual signature being a statistical representation of pixels of the second image;
an identifier recognition component which extracts second identifier information from the second image;
a cryptographic key reconstruction component for reconstructing the symmetric cryptographic key that was used to encrypt the first image based on the second identifier information extracted from the second image and the first metadata, by encrypting, with the one way function, the second information and the first metadata and signing the encrypted second information and first metadata with the shared key, the reconstructed symmetric cryptographic key permitting the first encrypted image to be decrypted to regenerate the first image; and
at least one processor which implements the signature matching component,
identifier recognition component, and cryptographic key reconstruction component.

14. The system of claim 13, further comprising a condition computation component which determines whether a condition is met based on the metadata associated with the first image and metadata associated with the second image.

15. The system of claim 13, further comprising a first computer system, at a first location, which generates the symmetric cryptographic key and encrypted first image, and a second computer system at a second location, which includes the cryptographic key reconstruction component.

16. The method of claim 1, wherein the first image is an image captured of a vehicle at a first time and wherein the second image is an image captured of a vehicle at a second time.

17. A computer program product comprising a non-transitory memory storing instructions, which when implemented by a computer processor, perform a method for preserving privacy of evidence comprising:
receiving an encrypted first image which has been generated by encrypting a first image with a symmetric cryptographic key that is generated by encrypting, with a one way function, first information extracted from the first image and first metadata associated with the first image and signing the encrypted first information and first metadata with a shared key, wherein the first metadata comprises a first time;
establishing a link between a second image and the first image comprising comparing a first visual signature computed based on the first image with a second visual signature computed based on the second image, each of the first and second visual signatures being a statistical representation of pixels of the respective image;
when the visual signatures are found to match, receiving the first metadata;
extracting second information from the second image; and
reconstructing the symmetric cryptographic key that was used to encrypt the first image based on the second information extracted from the second image and the first metadata, by encrypting, with the one way function, the second information and the first metadata and signing the encrypted second information and first metadata with the shared key, the reconstructed symmetric cryptographic key permitting the first encrypted image to be decrypted to regenerate the first image.